
Note: this page was created while Georgia Tech was on the quarter system. The switch to semesters has caused a change in the ACO core curriculum. Therefore, while the following information is mostly accurate, students should consult with the examination committee to be sure that they know which topics will be covered on the exam.
To succesfully pass the ACO comprehensive examination, students should know (at least) the following topics from mathematics, computer science, and optimization:
Combinatorial Methods
Design and Analysis of
Algorithms
Graphs and Graph Algorithms
Computational Complexity Theory
Linear Programming and
Integer Programming
Convexity
Algebra
Topology/Linear Algebra
Probability
 Fundamentals of Counting: combinatorial identities, distribution and occupancy problems.
 Special Sequences: Stirling numbers, Fibonacci numbers, Catalan numbers.
 Generating Functions: ordinary and exponential generating functions, convolutions, the exponential formula, Lagrange inversions, asymptotics.
 Recurrence Relations: the method of characteristic roots for linear recurrences, use of generating functions, families of recurrence relations, divideandconquer recurrences.
 Sieving Methods: inclusionexclusion principle, derangements, the Mobius function and Mobius inversion.
 Polya Counting Theory: Permutation groups, Burnside's lemma, the cycle index, Polya's theorem.
 Tools of the Trade: the basic tools and terminology of algorithms analysis.
 Sorting and Order Statistics: quick sort, heap sort, merge sort, bucket sort, radix sort; linear time order statistics  analysis and lower bounds.
 Data Structures for Fast Algorithms: redblack trees, dynamic data structures, Btrees, Fibonacci heaps.
 Amortized Analysis: unionfind data structure.
 Dynamic Programming.
 Fast Fourier Transforms.
 Fundamentals: isomorphism, basic properties of trees, spanning trees (correctness of Kruskal's algorithm), counting spanning trees, Eulerian and Hamiltonian graphs.
 Connectivity: Maxflow Mincut theorem, Menger's theorem, the structure of 1, 2, and 3connected graphs (blocks, eardecomposition, contractible edges, Tutte's synthesis of 3connected graphs*).
 Matching: Hall's theorem, systems of distinct representatives, Tutte's 1factor theorem, Dilworth's theorem.
 Coloring: greedy coloring, Brooks' theorem, chromatic polynomial, highly chromatic graphs of large girth, Vizing's theorem, Erdosde Bruijn compactness theorem.
 Planar Graphs: Euler's formula, dual graphs, Kuratowski's theorem, 5color theorem, equivalents of the 4color theorem, graphs on surfaces.
 Perfect Graphs: classes of perfect graphs (bipartite graphs, comparability graphs, line graphs of bipartite graphs, chordal graphs, complements of the above), the perfect graph theorem (polyhedral proof).
 Extremal Problems: Turan's theorem, the problem of Zarankiewicz (only excluding C4).
 Ramsey Theory: Ramsey's theorem for pairs, Ramsey's theorem*.
 Random Graphs: lower bound for Ramsey numbers, highly chromatic graphs of large girth, properties of random graphs such as the number of edges, chromatic number, the clique number, connectivity, subgraphs, threshold functions, 01 law.
 Complexity measures for deterministic, nondeterministic and alternating Turing machines; standard complexity classes.
 Tape compression, linear speedup, hierarchy theorems, the padding technique.
 Relationships among complexity measures, Savitch's theorem.
 The notions of reducibility and completeness. Intractability: NPcompleteness and PSPACE completeness.
 The polynomial time hierarchy, probabilistic Turing machines.
 Formulations
 Primal, dual and revised simplex algorithms
 Duality and sensitivity analysis
 Degeneracy
 Farkas lemma
 Column generation and DantzigWolfe decomposition
 Polynomial time algorithms for linear programming
 Polyhedral theory
 Branchandbound method
 Integral polyhedra, totally unimodular matrices, balanced and totally balanced matrices
 Convex sets and cones, polytopes and polyhedra, polyhedral cones.
 Linear and affine structure of R^d, transformations: linear, affine, projective.
 Theorems of Helly, Radon, and Caratheodory.
 Support properties, polarity.
 Euler's relation.
 Convex functions: criteria for convexity, epigraph, functional operations.
 Basic Group Theory: homomorphisms, cosets, quotients, products.
 Ring Theory: ideals, quotients, integral domains, rings of polynomials.
 Factorization: factorization of integers and polynomials.
 Modules: free modules, matrices and bases, applications to linear operators.
 Finite Fields.
 Fundamentals of Topology: topological and metrical spaces, continuous maps, compactness, connectedness, completeness, separability.
 TwoDimensional Manifolds: constructions from polygons, orientability, classification.
 Homotopy: simplicial complexes, the fundamental group, covering spaces.
 Topology in R^n: norms, compact convex sets, fixedpoint theorems, Jordan curve theorem, invariance of domain.
 Vector Space Properties of R^n: normed linear spaces, duality, bilinearity, subspaces, flats, eigenvalues and eigenvectors.
 Convexity in Linear Spaces: continuous linear functionals, closure and interior, hyperplanes, convex functionals, HahnBanach theorem.
 Fundamentals: probability spaces, distributions, expectations, independence, conditional probability.
 Random Variables: expectation, variance, Chebyshev's inequality.
 Laws of Large Numbers: Bernoulli trials, weak and strong laws, law of iterated logarithms, variable distributions.
 Central Limit Theorem: applications for binomial distributions, for sums of random variables, with relation to the Poisson approximation.
 Stochastic Processes: random walks, expected duration, Markov chains, the Poisson process.

. . . . . . . . . . . . . .  
This page is maintained by the ACO Webmaster, at the School of Mathematics, Georgia Institute of Technology. Last modified: October 30, 2011
