### Purpose

The purpose of the Theory Qual is to try to establish whether a student can complete a reasonable PhD in algorithms and/or theoretical computer science. The Theory Qual is primarily a written exam, designed to test both depth of knowledge and problem-solving ability. However, the committee’s decision to pass or fail a student depends not only on their exam performance, but also on their past coursework, previous research output (if any), and input from their advisor and other faculty members. The examination is offered in the fourth or fifth week of every semester.

Many previous quals are available in Sariel’s archive*.

*Sariel maintains an archive of past qualifying exams. While it is in your best interest to do as many of the problems as you can, note that the format of the exam changed in 2012. Prior to Spring 2012, the format was 5 problems with a time allocation of 3 hours for each exam. Since Spring 2012, the format has been 4-5 problems with a time allocation of more-or-less the whole day for each exam.

### 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. Theory students should ideally include CS 473 and CS 579 in their proposed course plan (unless they have taken equivalent courses elsewhere).

In addition to the core requirements, students are *strongly* advised to meet the following conditions before attempting the theory qual:

- Take at least one other graduate-level theory course beyond 473 and 579. Some post-qual theory PhD students recommend taking Math 580.

- Meet
**in person**with at least three theory faculty to discuss your background, your research interests, and our expectations for your performance on the exam.

- Solve
*all*(or in practice as many as possible) of the problems in the archive of past quals. Your first attempt at each problem should be under exam conditions: 45 minutes with no books, notes, or internet.

### Format

Traditionally, the theory qual is a closed-book written exam, given in two separate sections on two consecutive days. One section of the exam covers *mostly* algorithms and data structures, and the other *mostly* automata and complexity theory, although there is necessarily some overlap between those two concentrations. 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 examination is based on material normally covered at an introductory level in CS 473 and CS 579. **However, candidates are expected to have a deeper understanding of this material than required to get an A in both CS 473 and CS 579.** In addition, candidates are expected to be familiar with fundamental concepts in discrete mathematics and mathematical logic, such as those contained in standard undergraduate introductory textbooks.

Sources that may prove useful for studying for the qual include the following:

**Both sections:**- Faculty teaching materials
- Recent FOCS, STOC, and SODA proceedings

**Algorithms and data structures:**- Jon Kleinberg and Eva Tardos.
*Algorithm Design*, Addison-Wesley, 2006. - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
*Introduction to Algorithms*, 3rd edition. MIT Press, 2009. - Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani.
*Algorithms*, McGraw-Hill, 2006.

- Jon Kleinberg and Eva Tardos.
**Complexity and automata:**- Sanjeev Arora and Boaz Barak.
*Complexity Theory: A Modern Approach*. Cambridge, 2009. - Christos Papadimitriou.
*Computational Complexity*. Addison-Wesley, 1994. - Michael Sipser.
*Introduction to the Theory of Computation*. PWS Publishing, 2005. - Michael R. Garey and David S. Johnson.
*Computers and Intractability: A Guide to the Theory of NP-Completeness*. Freeman, 1983. - John Hopcroft and Jeffrey D. Ullman.
*Introduction to Automata Theory, Languages, and Computation*, 1st edition, Addison-Wesley, 1979.

- Sanjeev Arora and Boaz Barak.

If ** all** candidates in a given semester have taken an advanced course on some special topic, such as approximation algorithms or computational geometry, the exam

*may*also include questions on that topic. This is especially likely if the topic overlaps the candidates’ declared research interests.

Finally, in many semesters, the qual includes at least one open-ended question that the candidates cannot be reasonably expected to solve under exam conditions. With these questions, the faculty are looking for insight in how candidates approach hard problems. Do you have lots of half-baked ideas? Do you break the problem down into clear subproblems? Do you have good intuition about what techniques may be useful? Can you solve an interesting special case? Can you solve a closely related problem? Do you give up too easily? Or not easily enough?

### Evaluation

The examination committee consists of the entire algorithms and theoretical computer science research group (Chandra, Dakshita, Jeff, Michael, Ruta, Sariel, and Timothy), possibly with additional faculty from outside CS (Jugal and Karthik) and/or from closely-related research areas (Mahesh, Madhu, Tandy, Brighten, Sheldon, Matus, Edgar, etc.). Each faculty member typically contributes one or two questions to each semester’s exam.

The examination committee reviews the performance of all candidates, and renders a decision to pass or fail. The difficulty of the exam varies from semester to semester, but as a rough guide, a passing candidate submits near-perfect solutions to at least three of the eight qual problems and show significant progress on at least six. The committee’s decision depends not only on the candidate’s performance on the actual exam, but also on the candidate’s past coursework, their previous research output (if any), and input form their advisor and other faculty members the candidate has worked with. The committee may also impose additional conditions on a pass, such as additional coursework, to compensate for observed weaknesses.

In the last five years, roughly 60% of the students who took the theory qual passed 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.