UPDATES:

• Here are notes from the final exam review session, which includes sketches of the solutions we worked out for Problem 4.
• Along with the caveats below on directed vs. undirected, I also assumed HAMPATH takes as input a designated start and finish vertex. The textbook takes only a graph as input and asks about the existence of a Hamiltonian Path. Please do use the textbook’s definition, although you are free (given my error!) to use either one on the exam. (It’s a lovely exercise to reduce one to the other in either direction!)
• Check out video sample solutions to all except the memoization/DP problem. I’m not likely to have time to create a video walkthrough of that one; I skipped it b/c you already have previous video walkthroughs of similar problems.NOTE: I described all of HAMPATH, HAMCYCLE, and TSP in their undirected forms. The directed versions would be totally reasonable to work with as well.Here is the soln PDF I produced from the videos (which may be hard to follow, especially for the proofs of correctness/polynomial time for the reductions, which I only narrated).
• The word “smallest” was added in one of the “O(1) Answer Questions”. Front page of notes from Midterm #2 included.
• 3-D Matching will not play a critical role on the real exam (although it does on the practice).

Below are some practice problems for the final exam. These should be great practice for the exam, and if you do not at least read through them, you’ll be at a huge disadvantage.

However, please don’t believe that just reading through or even working through these is all you need to prepare! We have lots of other resources: sample exams from previous terms, our own midterms and practice midterms, the textbook and its problems, our assignments, and tutorial problems.

As always, please post if you have any questions! I do hope to post screencasts of solutions to at least large portions of these practice problems, but don’t bet your farm (or CPSC 320 grade) on it happening really soon 🙂

CPSC 320 2014W2 Final Exam Practice Questions

P.S. One comment on NP-completeness: Besides SAT and SP (the Steiner Tree Problem) that we discussed in class, I’ve listed every “well-known” NP-complete problem I expect you to be familiar with going into the exam in “Clark Kent’s Glasses”. All of these are at least briefly summarized in the last section of Chapter 8 except Knapsack, for which I provided a page reference.