PhD Qualifying Examination in
Algorithms and Theoretical Computer Science

The "Theory Qual" is designed to test both the depth of knowledge and the problem-solving ability necessary to do high-quality research in algorithms and theoretical computer science. The examination is offered in the fourth or fifth week of every semester.

Prerequisites

The candidate must have satisfied all PhD core coursework requirements and must have a signed doctoral advisor agreement on file in the Academic Office before the examination begins. See the department's qual policy for more administrative details. In addition, students are strongly advised to meet the following conditions before attempting the theory qual:

• Take CS 473G, CS 475, and at least two 500-level theory courses; most theory students automaticaly meet this criterion by satisfying the core course requirements.
• Meet in person with each of the theory faculty to discuss your background, your research interests, and our expections for your performance on the exam.
• Solve all of the problems in the archive of past quals, preferrably under exam conditions.

Format

Traditionally, the theory qual is a closed-book written exam, given in two separate three-hour sections on a single day (morning and afternoon), for a total of six hours. The exact format of the exam will be announced several weeks in advance, but after the deadline for indicating intent to take the exam.

Syllabus

The syllabus and examination are based primarily on material from the following textbooks.

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 2nd edition. MIT Press / McGraw-Hill, 2001. (The old required textbook for both CS 273 and CS 473.)
• Jon Kleinberg and Eva Tardos. Algorithm Design, Addison-Wesley, 2006. (The current required textbook for 473.)
• John Hopcroft, Jeffrey D. Ullman, and Rajeev Motwani. Introduction to Automata Theory, Languages, and Computation, 2nd edition, Addison-Wesley, 2000. (The required textbook for CS 475.)

The candidate should be familiar with just about all of the material in these texts. In addition, it is expected that the candidate will be familiar with fundamental concepts in discrete mathematics and mathematical logic, such as those contained in standard undergraduate introductory textbooks. Candidates are expected to have a deeper understanding of this material than required to satisfy the theory core requirement in either CS 473G or CS 475.

Other sources that may be useful include the following:

• Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications, 2nd edition. Springer-Verlag, 2000.
• Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1983.
• Donald E. Knuth. The Art of Computer Programming, volumes 1-3. Addison-Wesley, 1997.
• Tom Mitchell. Machine Learning. McGraw-Hill, 1997.
• Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
• Christos Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing, 2005.
• Recent STOC, FOCS, and SODA proceedings.
• Faculty lecture notes.

Evaluation

The examination committee consists of the entire algorithms and theoretical computer science research group — Jeff Erickson, Sariel Har-Peled, Madhusudan Parthasarathy, Lenny Pitt, Edgar Ramos, and Mahesh Vishwanathan — possibly with additional faculty from closely related research areas. Typically each faculty member contributes one or two questions to each semester's exam.

The examination committee will review the performance of all candidates, and render a decision to pass or fail. The difficulty of the exam varies from semester to semester, but as a rough guide, a passing candidate will submit near-perfect solutions to at least three of the eight qual problems and show significant progress on at least six. The committee's decision will depend not only on the candidate's performance on the actual exam, but also on the candidate's past coursework and previous research output (if any). The committee may also impose additional conditions on a pass, such as additional coursework, to compensate for observed weaknesses. Roughly 1/3 of the students who take the theory qual pass unconditionally on their first attempt.

Questions?

If you have any questions about the theory qual, talk with any of the theory faculty or send Jeff email.