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.
- 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.
- 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).
- 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.