PLEASE NOTE: the Theory Exam is no longer offered; the syllabus of the new Algorithms Exam is different. However, many, but not all, problems from old theory exams require knowledge only of the new syllabus, and solving these problems may help you to prepare better for the Algorithms Exam.

Theory Exam Syllabus

Students must answer several questions from each of two areas. The first area is theoretical computer science. The second area is analysis of algorithms. A typical format will require students to answer roughly equal numbers of questions from both areas.

The material for the exam includes the following topics: formal languages and related machines, basic computability theory, space and time complexity measures; algorithms, data structures and their analysis, and NP-complete problems.

Recommended Bibliography

Cormen, Leiserson, Rivest, Introduction to Algorithms (Chapters 1-26.)
This is the primary reference for algorithms.

Aho, Hopcroft and Ullman, The Design and Analysis of Computer Algorithms (Chapters 1-5, 9-10.)

Davis & Weyuker, Computability, Complexity, and Languages (Chapters 1-10.)

Hopcroft and Ullman, Introduction to Automata Theory Languages and Computation (Chapters 1-8, 12-13.)

Sample Exams

Fall 2003 (Answers)
Fall 2002
May 2002
May 2001
May 1999
May 1998
Fall 1997
Fall 1996
Spring 1996
Fall 1995