CS 312 (W'07, T Th sections)

« Dr. RinggSyllabus for all sect | Main | Reminder:Syllabus for all sect »

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

Comments

Posted by: ringger at April 14, 2006 11:04 AM

Post a comment