Requirements for the Doctoral Program in ACO

Course Requirements

The Coordinating Committee for the Ph.D. program in Algorithms, Combinatorics and Optimization has established the following core curriculum. This curriculum is designed to provide students with significant flexibility in choosing courses, while simultaneously ensuring a solid grounding in the fundamentals of ACO. (Students entering the program prior to Fall 1997 may choose instead to follow the previous requirements.) More information on specific courses can be found in the home departments: CS, TSB, and Math.

The course requirements for the ACO doctoral program consist of 10 course semesters (counting minis as 1/2 semester): 3 semesters in Mathematics, 3 in Computer Science, and 3 in TSB, plus a semester of Probability Theory.

Mathematics:

CORE COURSE (required of all students):
Discrete Math (21-701)

2 of the following, at least 1 of which must be a starred option:
*Algebra (21-610)
*Real Analysis and Lebesgue Integration (21-620 and 21-621)
Numerical Analysis (21-660)
Methods of Optimization (21-690)

Computer Science:

CORE COURSE (required of all students):
Algorithms (15-750)

2 of the following:
Artificial Intelligence (15-780)
Computer Systems (15-740)
Programming Languages (15-711)
Software Systems (15-712)
Complexity Theory (15-855)
Security and Cryptography (15-827)
Theory of Performance Modeling (15-849)
Algorithms in the Real World (15-853)
Machine Learning Theory (15-859B)
or any course in the 15-85x numbering (upper-level algorithms/theory)

TSB:

CORE COURSES (required of all students):
One mini: Theory and Algorithms for LP
One mini: Graph theory
One mini: Integer programming

3 minis to be taken from:
Networks and Matchings
Advanced Integer Programming
Convex Polytopes
Advanced Linear Programming
Dynamic Programming
Nonlinear programming
Optimal Control Theory
Approximation Algorithms
Topics in Polyhedral Combinatorics
Packing and Covering
Computational Molecular Biology
Network Design Algorithms
Special Topics in OR

Students are also required to take one of the following courses in Probability Theory:

Probability and Combinatorics (15-8xx)
Probability Theory (21-780)
Probability Theory and Stochastic Processes I (36-753)
In addition, there is a qualifying examination covering the fundamentals of the program; The exam syllabus will take account of the choices of electives made by the particular set of students taking the exam. This examination will be given at the beginning of the student's fourth semester. Students are expected to have satisfied all course requirements by the end of the sixth semester.

In the event that a student has already mastered the material covered by a required course when entering the program, another course may be substituted with approval from the student's advisor in consultation with the ACO Coordinating Committee.

Research Requirements

During their residence at Carnegie Mellon, students in the Ph.D. program in Algorithms, Combinatorics and Optimization are expected to participate in the weekly ACO research seminar. Students are also expected to take advanced courses in the area of their research in addition to the course requirements listed above.

At the end of the third semester (if not earlier), students should choose a faculty member to supervise their research and dissertation. Throughout this period, they will be subject to an annual review by the ACO faculty. The ACO faculty will judge whether the thesis work is proceeding satisfactorily. Approximately a year before the expected graduation date, students must make a thesis proposal before a thesis committee, composed of the advisor and two or more faculty members of the student's choosing. The final transition point is the thesis defense, which is presented before the same committee.

To graduate, students will need some teaching experience, and all students must demonstrate programming skills. (For every student, a faculty member, approved by the student's advisor, would attest that the student has adequately demonstrated programming skills.)

Back to the ACO home page