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:
Design and Analysis of Algorithms
Graphs and Graph Algorithms
Computational Complexity Theory
Linear Programming and Integer Programming
- 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, divide-and-conquer recurrences.
- Sieving Methods: inclusion-exclusion 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: red-black trees, dynamic data structures, B-trees, Fibonacci heaps.
- Amortized Analysis: union-find 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: Max-flow Min-cut theorem, Menger's theorem, the structure of 1-, 2-, and 3-connected graphs (blocks, ear-decomposition, contractible edges, Tutte's synthesis of 3-connected graphs*).
- Matching: Hall's theorem, systems of distinct representatives, Tutte's 1-factor theorem, Dilworth's theorem.
- Coloring: greedy coloring, Brooks' theorem, chromatic polynomial, highly chromatic graphs of large girth, Vizing's theorem, Erdos-de Bruijn compactness theorem.
- Planar Graphs: Euler's formula, dual graphs, Kuratowski's theorem, 5-color theorem, equivalents of the 4-color 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, 0-1 law.
- Complexity measures for deterministic, nondeterministic and alternating Turing machines; standard complexity classes.
- Tape compression, linear speed-up, hierarchy theorems, the padding technique.
- Relationships among complexity measures, Savitch's theorem.
- The notions of reducibility and completeness. Intractability: NP-completeness and PSPACE completeness.
- The polynomial time hierarchy, probabilistic Turing machines.
- Primal, dual and revised simplex algorithms
- Duality and sensitivity analysis
- Farkas lemma
- Column generation and Dantzig-Wolfe decomposition
- Polynomial time algorithms for linear programming
- Polyhedral theory
- Branch-and-bound 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.
- Two-Dimensional Manifolds: constructions from polygons, orientability, classification.
- Homotopy: simplicial complexes, the fundamental group, covering spaces.
- Topology in R^n: norms, compact convex sets, fixed-point 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, Hahn-Banach 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