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:

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. 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:

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.