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
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.
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.)
Fall 2003 (Answers)
| contact firstname.lastname@example.org