Exam 4 Review Information

Exam 4 will be during the registrar-assigned final exam time period. Take care of any necessary business before class so that you do not need to leave the room during the exam. The exam is intended to be similar to the other midterms and take approximately an hour to an hour and a half, though you can use as much of the final exam time period as you would like.

Note that only your dean can reschedule this exam. If you have three exams on the same day, you may work with the instructor and your dean to reschedule one of them. To reschedule this exam, you must be in touch with me by the end of the day Wednesday 5/6.

The exam will be closed book, but you may use one page of notes (one side of an 8.5x11" piece of paper), which will be handed in with the exam. This page may be handwritten or typed and can contain whatever you would like, but it must be a hardcopy — on a piece of paper, not a laptop, tablet, phone, or other device — and must be personally prepared by you — you may not copy another student's page or hand out copies of yours to others. Creating your own notes is an essential part of the learning process — deciding what to include requires engagement with the material which reinforces understanding and improves long-term retention of the material, provides an opportunity for review in order to identify gaps in your knowledge in time to ask questions before the exam, increases confidence in what you do know, and encourages taking ownership of your own learning.

The exam will focus on algorithm development and complexity. (Other material will play a supporting role --- big-Oh and data structures come in when considering efficiency, for example --- 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 development process from class
• 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)

For the algorithm development processes, you will be provided with a listing of the steps without further description. (See the review/practice questions for an example of what to expect.) You should know (or include in your page of notes) what those steps mean/involve as well as the relevant patterns (easy split, easy merge, process input, produce output, etc) but you do not need to memorize what all of the steps are.

Homeworks 8-13 and the time-o programming assignment cover material that may be on the exam. Expect questions like those on the homeworks (developing an algorithm in a particular paradigm, identifying avenues for improving backtracking through pruning and branch-and-bound, NP-completeness reductions) as well as possibly short answer questions about definitions and concepts — aspects of the algorithmic paradigms and development processes, aspects of making backtracking practical, reductions, complexity, and strategies for dealing with NP-complete problems.