The final is worth 30 points. These will be distributed as follows:

• 10 points will be devoted to solving problems with dynamic programming
• 10 points will be devoted to our discussion corresponding to the Chapter on NP-completeness (Chapter 8).
• 10 points will be devoted to the following specific earlier topics: (a) Application of graph algorithms from Chapter 3; this will focus not on the details of the algorithms, but the contexts in which they can be applied. (b) The integer multiplication algorithm from Section 5.5, and in particular, an understanding of the two recurrences that show up there. (c) The minimum spanning tree algorithms and correctness from Section 4.5; we will not focus on the data structures for implementing Kruskal's and Prim's algorithms.