Final Exam Study Guide


The final exam will take place in the classroom. See the class schedule for details. You will have a 3 hour time limit. The exam is closed book, and you may have two pages of notes handwritten or typed by you. One of those two pages could be the page of notes you prepared for the mid-term exam (as long as they were in compliance with the policy in the syllabus). No calculators or digital assistants (you won't need one). I think a well-prepared student will be able to complete the exam in two hours. You’re going to do well!

The format could consist of any combination of short answers, worked mathematical solutions, multiple choice, or even some T/F.

Always be ready to show your work. You will be graded not only on the correctness of your answer, but also on the clarity with which you express your rationale for your answer; plan to be neat. It is your job to make your understanding clear to us; non-neat work is likely to earn a lower grade. If using a pencil (rather than a pen) helps you be neat, please plan accordingly.


I recommend the following activities to study the topics covered by the exam:

  • Review the lecture notes and identify the topics we emphasized in class. Prepare your notes. This process will probably be your best preparation.
  • Compare the homework solution keys to your homework assignments, and make sure that you understand the major principles covered in the homework problems.
  • Consider how to apply the problem solving strategies we have worked with: draw a decision tree that enables you to choose a problem-solving strategy for any given new problem. Assume that you, Google,, and everywhere else on the web do not know the solution to the problem! Clearly identify the following:
    • the questions at each branching point (probably binary questions; make sure that your questions are about the nature of the problem or about a simple step you can try)
    • the answers along each branch (usually yes/no)
    • the chosen strategy at each leaf (be sure that the leaves of your decision tree include LP, DP, Div&Conquer, Graph, State-space search, Solution-space search, Greedy, if possible)


The final exam is comprehensive and will cover the following:

  • Topics from the first half of the semester (refer to the Mid-term Exam study guide for possible topics) with a focus on questions emphasizing synthesis across all course topics
  • Topics from the last half of the course, including a subset of the following topics:
  1. Greedy algorithm for computing (divisible) knapsack loads
  2. 0/1 Knapsack using DP
  3. Formulating Dynamic Programming algorithms for unfamiliar problems
  4. Formulating problems as Linear Programming problems
  5. Expressing a Linear Programming problem in Standard Form in preparation for solution by the Simplex Method
  6. Pivoting an LP problem as part of the Simplex Method
  7. Solving an LP problem using algebra
  8. Network flow algorithm
  9. Formulation of network flow as a linear programming problem
  10. Correspondence between the network flow algorithm and the simplex algorithm
  11. Minimum cuts
  12. NP-completeness: definition and how to prove that a problem is NP-complete
  13. Design decisions involved in creating and implementing Back-tracking search algorithms
  14. Reasoning about the completeness of search algorithms
  15. Design decisions in creating and implementing Branch and bound optimization algorithms
  16. Reasoning about optimality of B&B algorithms
  17. Solving the Job Assignment problem with a branch and bound algorithm
  18. Solving the TSP with a branch and bound algorithm
  19. Formulating B&B algorithms for unfamiliar problems
  20. Relationships among A*, Branch and Bound, Dijkstra’s, and Uniform Cost Search
  21. Admissible heuristics for A*; relationship to bound functions for B&B
  22. Solution-space search: local search and its variants
  23. Elementary probability theory and its relevance for average case analysis
  24. NO rederivation of the average case analysis of Quicksort
  25. Convolution
  26. Asymptotic analysis of the efficiency of the Fast Fourier Transform
  27. NO complex n-th roots of unity
cs-312/final-exam-study-guide.txt · Last modified: 2015/04/17 07:35 by ringger
Back to top
CC Attribution-Share Alike 4.0 International = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0