Information for Comprehensive Exam 

Computer Science 751: Analysis of Algorithms
Lehman College, City University of New York

General Information

• The comprehensive exam is Saturday, 29 March.
• It will cover similar material that covered by the final:
  • Chapters:
    I: Foundations: Analyzing algorithms, Designing Algorithms, Summations, Growth of Functions, Recurrences,
    II: Sorting: Heapsort, Quicksort, Sorting in Linear Time, Lower bounds for sorting
    III: Hash Tables, Binary Search Trees
    IV: Dynamic Programming, Greedy Algorithms
    VI: Elementary Graph Algorithms, Minimum Spanning Trees, Single-Source Shortest Paths
    VII: Matrix Operations, String Matching, NP-Completeness, Approximation Algorithms 
  • Lecture notes,
  • Quizzes 1-8, and
  • Handouts from the webpage.

Exam Rules

• The exam is closed book and closed notes.
• You may not use a computer or calculator.
• You will have 3 hours to complete examinations on 3 different topics.  

How to Prepare

• Do the assigned reading.
• Make sure you do all the problems that have been assigned. The problems (or parts of them) make excellent exam questions.
• Here are some exams I've written for algorithms courses in the past:
  
  • Exams from the course in the Fall:
    
    • First midterm exam
    • Second midterm exam
    • Final exam 
  • Masters Algorithms course from Winter 1998.  They were several different versions of the exam due to limit cheating.  Each version had 10 questions altogether.  Here are all of the questions in one file for their first exam and their second exam. 
  • Doctoral Algorithms course from Fall 2001.  We covered about three times as much material in that course and in much more depth.  So, that exam has much harder questions over more material than our exam will.