COS 216: Algorithms

Spring 2022

Final exam information

1. Allowed materials

During the exam:

• You are strongly discouraged to use the textbook, your notes, homework, and PDFs I've given you.
• You are not allowed to use other resources (Internet search, friends, etc.).
• You may only use electronic devices (computer, smart phone) to the extent of following exam logistics (below).

2. Exam content

The exam covers everything we have done. The exam is cumulative, so you should review the topics of the previous three exams. Here are some topics we emphasized since the last exam:

• complexity theory (chapter 8)
  • polynomial-time reductions: Karp reduction
  • reframing problems as decision problems/sets
  • NP: verifier definition, proving problems are in NP
  • NP-complete: in NP and NP-hard, via Karp reductions
  • famous/standard NP-complete problems:
    • boolean satisfiability: CircuitSAT, SAT, CnfSAT, 3SAT, 1-in-3SAT
    • graph problems: IndependentSet, VertexCover, $k$-Colouring, Euler (in P), Hamilton, TSP
    • numerical problem: SubsetSum
    All of the above (save Euler) are NP-complete.
  • P vs. NP
    • consequence for proving P=NP
    • for now, assuming P $\neq$ NP, purpose/consequence of proving a problem NP-complete
• data structures: abstract data types (ADTs) and common implementations, big Oh bounds of common operations
  • Map ADT: Init, Add, Lookup, Contains, Remove
  • hashing
    • hash table to implement Map ADT
    • separate chaining
    • open addressing
    • load factor, rehashing

As usual, please note that this document is not a contract. I may have inadvertently left something off that ends up on an exam question. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.

3. Logistics

Logistics will be largely similar to Exam 1; review it if you don't remember the procedure. The only change is that it is during our officially scheduled final exam period, which runs for 2 hours.