What to study for the final

The sample final is meant to be a template for the actual final. The parts of the actual final are in 1-1 correspondence with those of the sample final. There should also be a large resemblance between the midterm and homework and various parts of the final.
  1. First question: Order notation, True and false. Review: Chapter 1, Appendix A, Order notation summary sheet, First homework, first part. Midterm, first question.
  2. Second question: Divide and conquer. Review: Chapter 2, Appendix B, Second homework: all but last two questions. Midterm: fourth question.
  3. Third question: Back-tracking and dynamic programming. First two parts: time analysis and example for backtracking. Review: Chapter 5, Backtracking summary sheet; Second homework, last two problems. Fourth homework, initial solutions.
  4. Second two parts: convert to dynamic programming. Review: Chapter 3, Dynamic programming summary sheet, fourth homework.
  5. Fourth question: Greedy algorithms and fast versions of algorithms: First several parts: greedy algorithms. Review: Chapter 4, Greedy Algorithms Summary Sheet; third homework.
  6. Last part: fast versions of algorithms. Review: Chapter 7.6 (heaps), Chapter 8.3, Appendix C, Using Data Structures Summary Sheet, Lecture notes. Homework 1, triangles and Energy Crisis problems. Midterm questions 2 and 3. Homework 3, fast versions of greedy algorithms.