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.