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 NPcomplete problems.
Recommended
Bibliography
Cormen, Leiserson,
Rivest, Introduction to Algorithms (Chapters 126.)
This is the primary reference for algorithms.
Aho, Hopcroft and Ullman, The Design and Analysis of
Computer Algorithms (Chapters 15, 910.)
Davis & Weyuker, Computability, Complexity, and
Languages (Chapters 110.)
Hopcroft and Ullman, Introduction to Automata Theory
Languages and Computation (Chapters 18, 1213.)
Sample
Exams
Fall 2003 (Answers)
Fall 2002
May 2002
May 2001
May 1999
May 1998
Fall 1997
Fall 1996
Spring 1996
Fall 1995
top  contact webmaster@cs.nyu.edu
