The Comprehensive Examination in algorithms is meant to cover approximately the material in Comp 382 plus prerequisites. The textbook is quite large and the 382 instructor will probably not have time to cover all of the sections required for the algorithms exam. Here we present a list of topics and a reading list to describe the covered material.

The textbook is Introduction to Algorithms by T.H. Cormen, C.E. Leiserson and R.L. Rivest, MIT Press, 1990. All chapter and section numbers below refer to this book. The topics are given in the order in which they are discussed in the book. Chapters 17, 27-32, and 35 are not required; a few other sections are omitted, as noted below.

Topics covered by the exam:

Mathematical Foundations (Chapters 1-5, 6.1-6.4, 6.6)

• Introduction to Algorithms (Ch. 1)
• Asymptotic Notation (Ch. 2)
• Simple Summations (Ch. 3)
• Solving Recurrences (Ch. 4)
• Sets, Functions, Relations, Graphs (Ch. 5; primarily tested on Foundations Exam)
• Elementary Combinatorics and Probability (Sec. 6.1-6.4, 6.6)

• Heapsort, Quicksort, Mergesort (Ch. 7-8)
• Sorting lower bounds (Sec. 9.1)
• Radix sort, Bucket sort (Ch. 9)
• Order Statistics (Ch. 10)

• Pointers, stacks, queues, and their implementation (Ch. 11)
• Hashing (Ch.12)
• Binary Search Trees (Ch. 13)
• Red-Black Trees (Ch. 14)

• Dynamic Programming (Ch. 16)
• Amortized Analysis (Ch. 18)

• B-Trees (Ch. 19)
• Binomial Heaps (Ch. 20)
• Data Structures for Union-Find (Ch. 22)

• Basics (Ch. 23)
• Minimum Spanning Tree Algorithms (Ch. 24)
• Shortest Paths Algorithms (Ch. 25-26, except Sec. 25.3)

• NP-Completeness and Approximation Algorithms (Ch. 36, 37)