Computer Science Comprehensive Exam
Algorithms Syllabus
1997-1998
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)
Sorting and Order Statistics (Chapters 7-10)
- Heapsort, Quicksort, Mergesort (Ch. 7-8)
- Sorting lower bounds (Sec. 9.1)
- Radix sort, Bucket sort (Ch. 9)
- Order Statistics (Ch. 10)
Basic Data Structures (Chapters 11-14)
- Pointers, stacks, queues, and their implementation (Ch. 11)
- Hashing (Ch.12)
- Binary Search Trees (Ch. 13)
- Red-Black Trees (Ch. 14)
Other Fundamental Design and Analysis Techniques (Chapters 16 and 18)
- Dynamic Programming (Ch. 16)
- Amortized Analysis (Ch. 18)
Advanced Data Structures (Chapters 19, 20, 22)
- B-Trees (Ch. 19)
- Binomial Heaps (Ch. 20)
- Data Structures for Union-Find (Ch. 22)
Graph Algorithms (Chapters 23-26, except Section 25.3)
- Basics (Ch. 23)
- Minimum Spanning Tree Algorithms (Ch. 24)
- Shortest Paths Algorithms (Ch. 25-26, except Sec. 25.3)
Miscellaneous Topics (Chapters 36, 37)
- NP-Completeness and Approximation Algorithms (Ch. 36, 37)