« Lecture 21 | Main | Homework Keys 13-15 »
June 19, 2006
Final Exam Study Guide
Here is a list of things you might want to study in order to be well prepared for the final exam:
- Make sure you understand the concepts from the homeworks
- Understand the minimax algorithm.
- How to prove that a problem is NP complete.
- Floyd's algorithm / shortest paths
- Principle of Optimality
- Deriving the big-Theta bounds for certain kinds of divide-and-conquer algorithms using the methods for solving recurrence relations covered in class. In particular, be sure to be able to do the first problem in the last homework assignment on recurrences. This will involve knowing some logarithm and exponent identities.
- How to turn a problem description into a linear programming problem using standard form, slack form, or simplex form (know all three ways).
- Understand the various knapsack problems
- Understand how depth-first and breadth-first search work.
- Design decisions in creating and implementing branch and bound algorithms.
- Basics of solving the TSP with a branch and bound algorithm.
- How to compute amplification of stochastic advantage for repeated Monte Carlo algorithms.
- How to compute speedup and efficiency for parallel algorithms and how to tell if a parallel algorithm is good or not.
If you study these topics, and understand them, you should be ready for the final.
Posted by ryanShepherd at June 19, 2006 04:42 PM
Comments
Post a comment
Thanks for signing in, . Now you can comment. (sign out)
(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)