22C:31 Algorithms Final Information

The final exam is an in-class exam between 12:00 noon and 2:00 pm on Friday, 12/18. You are free to bring and use textbooks, class notes, solutions we have provided, etc.

The exam will focus on the two most recent topics we have studied, namely dynamic programming (Chapter 6) and NP-completeness (Chapter 8). However, the exam is comprehensive in the sense that you might have to use skills acquired while studying earlier chapters (e.g., asymptotic analysis, constructing counter-examples to greedy algorithms, etc.). For NP-completeness you should focus on Sections 8.1 through 8.5.

There will be 2 problems on the exam and I expect each problem will take you about 45 minutes total, i.e., from reading the problem and understanding it to thinking about it to neatly writing up a solution. Here are a few more details about each of the problems.

• Problem 1 on dynamic programming consists of two parts. In part (a), you will be given a partial or an incorrect solution and you have to complete it or correct it. In part (b), you will have to construct a dynamic programming solution to a given optimization problem from scratch (like you did for problems in Homework 5).

• Problem 2 on NP-completeness consists of two parts. In part (a), you will be given some claim (about efficient certifiers or poly-time reductions or some such concept) and you will have to determine if the claim is true or false and provide some justification. In part (b), you will have to show a given problem NP-hard by constructing a polynomial-time reduction from a known NP-hard problem to the given problem.