« ProjectedSyllabus for all sect | Main | Lecture #Syllabus for all sect »
April 17, 2006
Final ExaSyllabus for all sect
For the CS 312 Final in sections 002 and 003, I encourage you to prepare in such a way that you will be comfortable with the following topics:
- Definitions of Big-O, Big-Omega, Big-Theta
- How to prove that a problem is NP complete.
- 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 backtracking algoirthms such as depth-first and breadth-first search work.
- The minimax algorithm.
- Design decisions in creating and implementing branch and bound algorithms.
- Basics of solving the Job Assignment and TSP problems with branch and bound algorithms.
- How to compute amplification of stochastic advantage for repeated Monte Carlo algorithms.
- How to express a Linear Programming problem in Slack Form in preparation for solution by the Simplex Method.
- How to compute speedup and efficiency for parallel algorithms and how to tell if a parallel algorithm is good or not.
The exam will include:
- about 20% material from the first two-thirds of the semester as well as questions requiring synthesis across the course topics
- about 80% material from the latter third of the course (since the second mid-term).
The exam is reasonable. I think a well-prepared student will be able to complete the exam in less than two hours.
You will do well!
--Eric
Posted by ringger at April 17, 2006 11:02 AM
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.)