PhD Quals

PhD QUALIFYING EXAMINATION -- Analysis of Algorithms

The examination procedure will be as follows. Each year an AA faculty member will be designated a quals coordinator. For each student taking the qual, the coordinator will appoint a 3-member committee. The committee, in consultation with the student, will select a topic. (Examples of topics are: approximation algorithms, data structures, primality testing, distributed graph algorithms.) Then the committee selects a set of (typically 3) papers in the chosen area.

The student is expected to read the papers and thoroughly understand the results and the proof techniques. To demonstrate this understanding to the committee, the student can come up with a unified framework that can be used to explain/prove the results presented in the papers and to show the relationship between them. Also, the student is expected to explain how these results mesh with the previous work in that area. Simplifying the arguments in the papers is desirable.

Sometimes a better framework leads to a better understanding which, in turn, leads to new publishable results. Although the student is not required to produce a publishable paper, producing such a paper essentially guarantees a passing grade.

The student has four weeks to prepare a report which is about 10 pages long. The oral part of the exam occurs within a week from the date the report is submitted. The oral part consists of a one hour presentation, open to the public, and a closed question session. During the closed session the student may be questioned on the material in the papers, as well as on background material related to the papers. The student is expected to be able to reconstruct proofs that were omitted from the papers.

During the oral part of the exam, the student may also be asked questions to test his/her general background. These questions will be restricted to the material covered by the AA qual reading list given below.

After the question session, the committee takes a vote to decide if the student passes or fails, and the student is immediately informed of the outcome. Afterwards, the student receives a letter with the feedback from the committee (e.g., keep up the good work, attend a specific course, improve writing skills). The committee also has an option to pass the student conditionally (e.g., subject to getting at least a ``B'' on a technical writing class).

The student is expected to work independently on all stages of the process. The student is allowed to discuss the material in the assigned papers only with the three committee members. Discussing the material with anyone else is forbidden; this includes discussion of the material in the papers, discussion of previous work, or discussion of different ways to present the material.

This exam can be taken at most two times.