Theory of computing

Qualifying exam

Preparatory courses

There are three introductory undergraduate courses in theory of computing:

  • CS 577 covers algorithm design and analysis.
  • CS 520 covers automata theory, computability theory, and computational complexity theory.
  • CS 435 covers cryptography.

CS 577 and CS 520 form the core that all graduate students in CS are expected to have taken before graduate school; undergraduates who intend to do graduate work in CS should take both.

At the graduate level there are two introductory courses that are offered every year:

  • CS 787 covers algorithms.
  • CS 710 covers complexity theory.

In addition, there are three more specialized regular courses (CS 809, CS 812, CS 830), as well as the topics course CS 880, which is a full-fledged course but with a topic that depends on the offering. Those courses may not be offered every year. All graduate students interested in theory of computing are encouraged to take CS 880 whenever it is offered.

Although the material for the qualifying exam in theory of computing does not stretch far beyond the material of CS 520 and CS 577, students preparing for the exam should take CS 710 and CS 787 before the exam.

Reading list

The purpose of this syllabus is to delineate the material for the qualifying exam in theory of computing. You should feel free to use other sources to learn the material. Most of it is covered in at least one of CS 520, CS 577, CS 710, and CS 787. However, the material for the exam is defined by the list below and not by the latest offerings of the theory courses.

  • Algorithms:
    • Kleinberg and Tardos, Algorithm Design, Addison Wesley, 2006: entire book.
    • Motwani and Raghavan, Randomized Algorithms, Cambridge University Press, 1995: Part I.
  • Complexity:
    • Sipser, Introduction to the Theory of Computation, 2nd edition, Course Technology, Cencage Learning, 2006: entire book.
    • Arora and Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009: Part I.

You are also expected to know basic mathematics, as described in the appendix of the text by Arora and Barak.

Past exams

  • Fall 2017 (pdf)
  • Spring 2017 (pdf)
  • Fall 2016 (pdf)
  • Spring 2016 (pdf)
  • Fall 2015 (pdf)
  • Spring 2015 (pdf)
  • Fall 2014 (pdf)
  • Spring 2014 (pdf)
  • Fall 2013 (pdf)
  • Spring 2013 (pdf)
  • Fall 2012 (pdf)
  • Fall 2011 (pdf)
  • Fall 2010 (pdf)
  • Spring 2010 (pdf)
  • Fall 2009 (pdf)
  • Spring 2009 (pdf)
  • Fall 2008 (pdf)
  • Spring 2008 (pdf)
  • Fall 2007 (pdf)
  • Fall 2006 (pdf)
  • Fall 2005 (pdf)
  • Spring 2005 (pdf)
  • Fall 2004 (pdf)
  • Spring 2004 (ps)
  • Fall 2003 (ps)
  • Fall 2001 (ps)
  • Spring 2001 (ps)
  • Fall 1999 (ps)
  • Fall 1998 (ps)
  • Spring 1998 (ps)
  • Fall 1996 (ps)
  • Spring 1996 (tex)
  • Fall 1995 (tex)
  • Fall 1994 (ps)
  • Spring 1994 (ps)
  • Fall 1993 (Depth) (ps)
  • Spring 1993 (Depth) (ps)
  • Spring 1993 (Breadth) (ps)
  • Spring 1992 (Depth) (ps)
  • Spring 1992 (Breadth) (ps)
  • Fall 1991 (Depth) (ps)
  • Spring 1991 (tex)
  • Fall 1991 (Breadth) (ps)
  • Fall 1991 (Depth) (ps)
  • Spring 1991 (tex)
  • Fall 1990 (tex)
  • Spring 1990 (tex)
  • Fall 1989 (tex)
  • Spring 1989 (tex)