April 13, 2006
Section 0Syllabus for all sect
The exam, and key, have been written. If I were studying for the final exam, I would want to be sure I was comfortable with the following topics:
- How to prove that a problem is NP complete.
- Derrive the big-Theta bound for certain kinds of divide-and-conquer algorithms using the methods for solving reccurence relations described in class. In particular, be sure I could do the first problem in the last homework assignment on reccurences. This will involve knowing some logrithm and exponent identities.
- Understood how depth-first and breadth-first search work.
- Understood the minimax algorithm.
- 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.
As you can see, the exam includes about 20% material from prior exams and about 80% material from later topics. The exam is pretty reasonable. Questions were deleted and modified during the creation of the key. It took me 30 minutes to write the key (remember that I only ask questions for which I already know the answer) including time to rewrite or delete certain questions. I think a well-prepared student could complete the exam in about 1 hour and 15 minutes.
Posted by jones at April 13, 2006 10:35 AM
This is reasonably close to my expectations as well. I will post a more precise list of topics on Monday 4/17.
Posted by: ringger at April 14, 2006 11:04 AM
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.)