Computer Science 477/677
Design and Analysis of Algorithms

CSC 477/677 Study Guide for the First Midterm Examination Fall 2009

  1. Review the homework assignments.
  2. There will be some true/false and fill-in-the-blank questions.
  3. I have posted exams from prior semesters. If a question that you see on one of those exams is not related to anything we've covered in class so far this semester up to the last class day before the exam, then don't worry: it will not be on our September 29 exam.
  4. You should understand what an asymptotic complexity class is, and be able to solve the kinds of recurrences we did in class.
  5. You should know the meanings of various terms, for example, single-source shortest path problem, knapsack problem, and minimum spanning tree problem. (Those are only examples. There are more.)
  6. You should understand the following abstract data types and their implementations:
  7. You should understand dynamic programming.
  8. Specific algorithm you should know: