Final Exam Review Information

The final exam will be a take-home exam. You may use the textbook, your own notes and problem solutions, the materials posted on the course website, and external websites directly linked from the course website. You may not use other resources, including web resources linked from things the course website links to. You may not get notes or other materials from or share notes or other materials with other students once the exam has been handed out, even if those notes/materials aren't directly related to the exam.

The only person you may discuss the exam with is me — I will answer clarification questions, but the exam is meant to be a demonstration of what you can do so I will not provide help on how to solve the problems.

Part I - Required

The required part of the exam will focus on algorithm development and complexity. (Older material may appear as relevant, but there won't be questions solely about that material.) Specific topics include:

• modeling problems as graph problems (including a familiarity with the common graph algorithms discussed in class)
• the development of divide-and-conquer algorithms
• the development of series-of-choices algorithms: greedy, recursive backtracking, and dynamic programming
• techniques for improving recursive backtracking, including what they are, when they are applicable, and what any drawbacks are
  • pruning
  • branch-and-bound
  • best-first search (including A*)
• reductions, including what a reduction is, how to apply the technique to solve a problem, and how to determine the running time of the resulting algorithm
• complexity and NP-completeness, including why NP-complete problems are important, some examples of NP-complete problems, and how reductions are used to prove that problems are NP-complete

"The development of ... algorithms" means

• being able to apply the appropriate n-step process
• knowing common patterns for algorithms of that type
• using the steps and patterns to develop an efficient algorithm and argue its correctness
• determining the running time of the algorithm (including making appropriate implementation choices and solving recurrence relations)
• identifying what paradigms are appropriate/applicable for a problem (e.g. when divide-and-conquer is applicable, or when greedy or dynamic programming is applicable instead of recursive backtracking)

Homeworks 13-25 cover material that may be on the exam. Expect problems similar to the kinds of things that you've been asked on the homeworks, though there may also be short answer questions about aspects of the algorithm development process (e.g. giving counterexamples for greedy choices or identifying appropriate loop invariants) and definitions and concepts related to reductions, complexity, and NP-completeness.

Part II - Optional

There will also be three additional sections, focusing on topics covered by exam 1, exam 2, and exam 3, respectively. (See the review information for those exams for the topics covered and what to expect.) These sections serve as a redo opportunity for exams 1-3 — the score, if better, will partially replace your score on the earlier exam.