The ACO comprehensive examination covers the material specified in the syllabi. The examination is normally administered twice a year, before the beginning of the Fall and Spring semesters. The examination consists of two parts:
Part I: Graph Theory, Linear Inequalities, and Graduate Algorithms;
Part II: Design and Analysis of Algorithms, Probabilistic Methods and Combinatorial Optimization
Each part will be offered during each sitting and students may sign up for one or both parts. Students may repeat either part, but only the most recent score will count. Students will have five hours to solve the four problems of Part I (four hours for those writing three problems) and four hours to solve the three problems of Part II. For each problem there will be an authorized source, usually a book or two, same for each student. In addition to the authorized sources, each student will be permitted to bring his or her own notes and class materials. Effort will be made to select a well-lit room with ample desk space and comfortable chairs, such as Skiles 114.
Definitions. Own notes means notes the student created himself or herself, either handwritten or typed on the computer; or photocopy of another student's class notes from a class taken at Georgia Tech; it does not include photocopy of someone else's work obtained elsewhere. Class materials mean materials distributed by professors during classes taken by the student, either in the form of handouts or downloads from the class website.
No electronic devices including cellular telephones are permitted during the examination.
Each student will be asked to sign an agreement stating the following: "I agree to work on the examination on my own and use only authorized sources. I will neither seek nor receive help from another person."
Each solution must be written on one side of a preprinted letter size form in black ink and delivered in good condition. In order to expedite grading solutions will be scanned and delivered to graders electronically. Anything that interferes with scanning will delay grading. Students should not write their name on the solution sheet. Grading will be done anonymously and each paper will be identified by a letter code.
The problems will be proofread beforehand to minimize the chance of errors. A designated faculty member will be available throughout the day should you have any questions or need clarification.
It normally takes at least two weeks before the results of the examination are finalized.
List of authorized sources for the comprehensive examination:
- Abstract Algebra by Dummit and Foote
- Algebra by Lang
- Approximation Algorithms by Vijay Vazirani
- Randomized Algorithms by Motwani and Raghavan
- Introduction to the Theory of Computation by Sipser
- Algorithm Design by Kleinberg and Tardos
- Modern Graph Theory by Bollobas
- Graph Theory by Diestel
- Combinatorial Optimization by Schrijver
- Theory of Linear and Integer Programming by Schrijver
- Probability and random processes by Grimmett and Stirzaker
- Probabilistic methods in combinatorics by Alon and Spencer
- Random graphs by Janson, Luczak, and Rucinski
- Matrix Analysis by Horn and Johnson
- Topics in Matrix Analysis by Horn and Johnson
