ACO - Typical Program of Study

Group theory:
subgroups and normal subgroups, homomorphisms, isomorphism theorems, groups acting on sets, orbits, stabilizers, orbit decomposition formula, Sylow theorems, permutation groups, simple groups, classification of groups of small order, simplicity of the alternating group on at least 5 letters, direct products and semi-direct products of groups, solvable and nilpotent groups, Jordan-Holder theorem, solvability of p-groups, free groups and presentations.
Rings and modules:
homomorphisms, prime ideals, maximal ideals, localization and field of fractions, principal ideal domains, unique factorization domains, group of units, Euler phi-function, structure theorem for modules over a principal ideal domain and its applications to abelian groups and to linear algebra, rational and Jordan canonical forms, eigenvectors, eigenvalues, minimal and characteristic polynomials, polynomial rings, Gauss' lemma, Eisenstein's criterion
Fields:
finite and algebraic extensions, algebraic closure, splitting fields, derivatives and multiplicity of roots, finite fields, primitive elements

Approximation Algorithms

Chapters 1-9, 12-15, 18-22 from V. Vazirani, Approximation Algorithms

Design and Analysis of Algorithms

Approximation algorithms:
Vertex cover, set cover, randomized rounding,
Traveling salesman problem,
Semidefinite programming,
Multicommodity flow
Randomized algorithms:
k-wise indpendence, quicksort,
Karger's min-cut algorithm,
Markov's inequality, Chebyshev's inequality, Chernoff bounds,
Balls and bins,
Expanders and spectral analysis
On-line algorithms:
Paging,
k-server,
Ski-rental
Computational geometry:
Finding convex hulls,
Voronoi regions and Delaunay triangulations

References:

Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
Randomized Algorithms by Motwani and Raghavan
Approximation Algorithms by Vijay Vazirani

Complexity

Complexity measures for deterministic, nondeterministic and alternating Turing machines; Standard complexity classes
Relationships among complexity classes; Savitchi's theorem, Non-deterministic Space closed under complement
The notions of reducibility and completeness
P-Completeness and the Circuit-value problem
NP-Completeness: Cook/Levin theorem, standard reductions
PSPACE-completeness: quantified Boolean formulas
Counting classes: the permanent problem
Randomized complexity classes: The class BPP; reducing error probability; BPP and the polynomial time hierarchy; log space probabilistic complexity classes
Interactive Proof Systems: IP = PSPACE
Relating the Probabilistic Checkable Proof systems characterization of NP and hardness of approximations

Graph Algorithms

Spanning trees:
Depth-first and breadth-first search spanning trees, minimum-weight spanning trees, Kruskal's and Prim's algorithms, the greedy algorithm and relation to matroids
Shortest paths:
Algorithms of Dijkstra, Bellman-Ford, Floyd-Warshall
Matchings:
Augmenting paths, bipartite matching, the Hungarian method, Edmonds' blossom algorithm, minimum weight perfect matching and Edmonds' matching polyhedron theorem, the Chinese postman problem, T-cuts and T-joins
Network flows:
The max-flow min-cut theorem and the associated algorithm, Hoffman's circulation theorem, Hu's 2-commodity flow theorem
Connectivity:
Vertex- and edge-disjoint paths in graphs, testing connectivity, decomposing a connected graph into blocks, Tutte's decomposition of a 2-connected graph into cleavage units ("3-connected pieces"), edge-connectivity, Gomory-Hu trees, the two disjoint paths problem
Coloring:
Theorems of Brooks and Vizing, edge-coloring bipartite graphs, 5-coloring planar graphs
Testing planarity:
Kuratowski's theorem, a planarity testing algorithm that runs in quadratic time or better
Directed graphs:
Testing connectivity of digraphs, decomposing a directed graph into strong components, ear decompositions, Roy-Gallai's theorem
Tree-width:
Basic properties, linear-time algorithms for problems on graphs of bounded tree-width

References:

Bollobas: Modern Graph Theory
Bondy and Murty: Graph theory with Applications
Cook, Cunningham, Pulleyblank and Schrijver: Combinatorial Optimization
Cormen, Leiserson and Rivest: Introduction to Algorithms
Diestel: Graph Theory
Papadimitriu and Steiglitz: Combinatorial Optimization

Graph Theory

Fundamentals
Isomorphism, trees, spanning trees (minimum-weight spanning trees, counting) bipartite graphs, contraction and minors, Eulerian and Hamiltonian graphs cycle space and cut space
Connectivity
Max-flow Min-cut theorem, Menger's theorem, the structure of 1-, 2-, 3- connected graphs (blocks, ear-decomposition, contractible edges, Tutte's synthesis of 3-connected graphs)
Matching
Hall's theorem, System of distinct representatives, Tutte's 1-factor theorem, Dilworth's theorem, stable matchings
Coloring
Greedy coloring, Brooks' theorem, Chromatic polynomial, highly chromatic graphs of large girth, Vizing's theorem, Erdos-de Bruijn compactness theorem, list coloring, perfect graphs, the Perfect Graph Theorem, the vertex packing polytope
Planar graphs
Faces and their boundaries, Euler's formula, Kuratowski's theorem, 5-color theorem, 3-edge-coloring 3-regular planar graphs, planar duality, testing planarity
Extremal problems
Turan's theorem, the problem of Zarankiewicz, minors
Ramsey theory
Ramsey's theorem for graphs, upper and lower bounds, Ramsey's theorem for k-tuples
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

References:

Bollobas, Modern Graph Theory
Diestel, Graph Theory

Integer and Combinatorial Optimization
During the transitional period until Spring 2009 this question will be written so that it can be solved using the knowledge of ISyE 7761 (see the syllabus below).

Networks (5 weeks)
- Shortest paths
- Max-flow/Edmonds-Karp
- Network simplex including flow integrality and duality
Integer Programming (5 weeks)
- Banch-and-bound
- Branch-and-cut
- Facets
- Chvatal-Gomory rank
- Polynomial equivalence of separation and optimization
Combinatorial Optimization (5 weeks)
- Spanning trees and matroids
- NP-completeness/Cook's Theorem
- Heuristics and approximation
- Matching

Linear Programming

Linear diophantine equations
Linear proramming duality, Farkas' lemma
Structure and complexity of polyhedra
Blocking and anti-blocking polyhedra
Integer polyhedra
Hilbert bases and total dual integrality
Cutting plane proofs and Chvatal cuts

References:

Schrijver, Theory of Linear and Integer Programming, pages 1-244, 309-359.

Probability

Fundamentals:
- Probability spaces, Distributions, Independence,
- Conditional probability
Random variables:
- Expectation, Variance
- Markov, Chebychev, Holder and other inequalities
- Various modes of Convergence
Laws of large numbers:
- Weak and Strong Laws, Borel-Cantelli Lemmas,
- Kolmogorov's zero-one law
Central limit theorem:
- Characteristic functions, Moment generating functions,
- The Central limit theorem, Poisson approximation.
Martingales and Stochastic Processes:
- Conditional Expectation, Random walks, Markov chains, Random Graphs
Large deviations
- Hoeffding, Chernoff, Azuma-Hoeffding, Talagrand inequalities

Suggested textbook:

G. Grimmett & D. Stirzaker, "Probability and random processes," 2nd ed., Oxford: Clarendon press; New York: Oxford university press, 1992.

For Random graphs and Large Deviations, see:

S. Janson, T. Luczak, and A. Rucinski, "Random Graphs," John Wiley & Sons, 2000.

Randomized Algorithms

Karger's min-cut algorithm
FPRAS for #DNF and Network Unreliability
Coupon collector's problem
Chernoff bounds
Balls and Bins, power of 2 choices
De-randomization: Conditional Expectation and Pairwise Independence
Hashing
Existence of expanders
Mulmuley-Vazirani-Vazirani's algorithm for perfect matchings
Reductions between approximate counting and random sampling
Markov chain basics
Random walks and cover times
Coupling method

References:

Randomized Algorithms by Motwani and Raghavan (Cambridge University Press, 1995);
Probability and Computing by Mitzenmacher and Upfal (Cambridge University Press, 2005).

<Plain-Text Page> (ACO Program Web Pages)

. . . . . . . . . . . . . .

This page is maintained by the ACO Webmaster,
at the School of Mathematics,
Georgia Institute of Technology.

Last modified: May 17, 2008

Georgia Tech Disclaimer:
Notwithstanding any language to the contrary, nothing contained herein constitutes nor is intended to constitute an offer, inducement, promise, or contract of any kind. The data contained herein is for informational purposes only and is not represented to be error free. Any links to non-Georgia Tech information are provided as a courtesy. They are not intended to nor do they constitute an endorsement by the Georgia Institute of Technology of the linked materials.