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.

Here are some practice probems for midterm #2.

It is likely to be tremendously useful to work through these problems, but as the first page warns, these may not be entirely representative of our exam.

Check out video sample solutions to all except the one that was on the first set of practice problems.

Here is the soln PDF I produced from the videos.

You can find all my sample solutions in my YouTube CPSC 320 playlist.

Here is the PDF of those written solutions. Be aware, however, that I generally focused more on talking through the solutions than writing them clearly; so, some solutions may make little sense without the video context.

Note that for 5.3 and 8.1 (and possibly a few others), I fell short of what I’d consider total closure on the question. 5.3 is a bit of a broken question; for 8.1, I’m satisfied with my possibly-loose answer (and wanted to move on to the more important 2nd and 3rd parts of the question).

Here are some old exams and sample exams (from previous terms). These are not my exams; so, I haven’t reviewed them, I do not have additional materials related to them that might be missing, and I don’t know how well they relate to what we’ve done so far.

(I can say that we have not yet discussed decision-theoretic lower bounds and may not do so, although many of you likely saw Ω(n lg n) bound on sorting by comparisons in CPSC 221, which is a decision-theoretic lower bound.)

Some of these require the login “cpsc320” and the solutions password for our course to access, which is posted on Piazza:

• 2014W1 First Sample Midterm #1 and its (password protected) sample solutions
• 2014W1 Second Sample Midterm #1 and its (password protected) sample solutions
• 2014W1 Sample Midterm #2 and its (password protected) sample solutions
• 2014W1 Sample Final Exam and its (password protected) sample solutions
• Password protected 2014W1 Midterm #1 sample solution (original not available)
• Password protected 2014W1 Midterm #2 sample solution (original not available)

Here are some practice problems for midterm #1.

It is likely to be tremendously useful to work through these problems, but as the first page warns, these may not be entirely representative of our exam. Indeed, we may not reach all the learning goals assessed in the practice problems by the exam; so, some of these may really be practice problems for midterm #2!