22C:31 Algorithms: Information about Final

The final exam will be between 9:45 am and 11:45 am on Tuesday, 5/11. Technically, the final is comprehensive. However, the focus will be on material covered since the last exam. Spefically, there will be three problems on the final, one on divide-and-conquer, one on dynamic programming, and one on NP-completeness. The exam is also open notes and open book. However, you will not be allowed to access your laptop or any other electronic device you may have on your person. Here are more details on each of the topics covered by the exam problems.

1. Divide-and-Comquer. You should study recurrence relations, how they help in analyzing divide-and-conquer algorithms, and how to solve them using the recursion tree method. You should study all of the examples of divide-and-conquer algorithms in the textbook (with the exception of Section 5.6), those that were covered in lectures, and those that appear in homework problems.

2. Dynamic Programming. You should study as many examples of dynamic programming solutions as you can, focusing on the step-by-step approach to designing dynamic programming algorithms, that I used in my lectures. Make sure you understand the importance of solving subproblems in a certain order, especially in the case of "2-dimensional" dynamic programming examples. Also, make sure you understand why the dynamic programming solutions to Subset Sum and Knapsack are not polynomial time algorithms (the running time of these is pseudopolynomial).

3. NP-completeness. You should study the definition of NP and how to show that a problem is in NP (by demonstrating the existence of an efficient certifier). You should study the definition of a polynomial-time reduction and also examples of such reductions we have seen in lectures (e.g., SAT to 3SAT, 3SAT to MIS, MIS to MVC, HAM CYCLE to TSP, etc.). You should study the definitions of NP-hard and NP-complete and be able to do very simple proofs of NP-completeness.