Some of the syllabi on this page have not
yet been approved by the Coordinating Committee and should not be regarded
as final.
Advanced Linear Algebra
 Characteristic and minimal polynomial. Eigenvalues, field of values
 Similarity transformations: Diagonalization and Jordan forms over
arbitrary fields. Schur form and spectral theorem for normal matrices.
Quadratic forms and Hermitian matrices: variational characterization of the
eigenvalues, inertia theorems
 Singular value decomposition, generalized inverse, projections, and
applications
 Positive matrices, PerronFrobenius theorem. Markov chains and
stochastic matrices. Mmatrices
 Structured matrices (Toeplitz, Hankel, Hessenberg). Matrices and
optimization (e.g., linear complementarity problem, conjugate gradient)
References:
 Matrix Analysis and Topics in Matrix Analysis
by Horn & Johnson
 Advanced Linear Algebra by Roman
 Linear Algebra and its applications
by Lax
Algebra
 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 semidirect products of groups, solvable
and nilpotent groups, JordanHolder theorem, solvability of pgroups, 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 phifunction, 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
Reference:
 Abstract Algebra by Dummit and Foote
Back to Top
Design and Analysis of Algorithms
 Approximation algorithms:
Vertex cover, set cover, randomized rounding,
Traveling salesman problem,
Semidefinite programming,
Multicommodity flow
 Randomized algorithms:
kwise indpendence, quicksort,
Karger's mincut algorithm,
Markov's inequality, Chebyshev's inequality, Chernoff bounds,
Balls and bins,
Expanders and spectral analysis
 Online algorithms:
Paging,
kserver,
Skirental
 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
Back to Top
Computability, Algorithms, and Complexity
 Computability theory:

Multitape Turing machines definitions; assume without covering
simulations of multitape and other variants. (Sipser sections 3.1, 3.2)
 Nondeterministic Turing machines; simulation of an NTM decider by a
DTM decider. (Sipser sections 3.2, 7.3)
 Decidability. (Sipser section 4.1)
 The Halting Problem is undecidable. (Sipser section 4.2)
 Reducibility: simple examples. (Sipser Sections 5.3, 5.1)
 Rice's theorem. (Sipser problem 5.28)
 Complexity theory:
 NPCompleteness: Definition of NP in terms of verification machines
(Sipser section 7.3); NPCompleteness, polynomialtime reducibility;
Cook/Levin theorem and its proof. (Sipser section 7.4)
 Reductions from satisfiability: 3cnfsat, clique, vertex cover,
Hamiltonian path, 3coloring, subset sum. (Sipser section 7.5)
 Decision versus computation: selfreducibility. (Sipser problem 7.36)
 BPP, amplification of acceptance probability. Polynomial identity
testing,
readonce branching program inequivalence problem, and other examples
(Sipser section 10.2)
NP is in BPP iff NP=RP (Sipser problem 10.19)
 Space Complexity: Savitch's theorem, PSPACECompleteness. (Sipser Chapter
8)
 Polynomial Hierarchy, time/space hieararchies
 Algorithms:
 Dynamic programming: Sequence alignment, Bellmanford shortest path
algorithm, finding negative cycles, FloydWarshall algorithm
 Minimum spanning trees and Shortest paths with advanced data
structures such as Fibonacci heaps and Unionfind data structures
 Maxflow: FordFulkerson algorithm, maxflow mincut theorem,
EdmondsKarp algorithm, scaling algorithm
 Matching: reduction from bipartite matching to network flow.
HopcroftKarp algorithm for bipartite maximum matching,
matching in general graphs (Edmonds algorithm)
 Fast Fourier transform: multiplication of single variable
polynomials; string matching
 Basic randomized algorithms: polynomial identity testing and other
examples
 Theory of Linear Inequalities
 Basic approximation algorithms: TSP, Steiner tree, Vertex cover
Reference:
 Sipser, Introduction to the Theory of Computation
Back to Top
Graph Theory
 Fundamentals
Isomorphism, trees, spanning trees (minimumweight spanning trees, counting)
bipartite graphs, contraction and minors, Eulerian and Hamiltonian graphs
cycle space and cut space
 Connectivity
Maxflow Mincut theorem, Menger's theorem, the structure of
1, 2, 3 connected graphs (blocks, eardecomposition, contractible edges,
Tutte's synthesis of 3connected graphs)
 Matching
Hall's theorem, System of distinct representatives, Tutte's 1factor theorem,
Dilworth's theorem, stable matchings
 Coloring
Greedy coloring, Brooks' theorem, Chromatic polynomial, highly chromatic graphs
of large girth, Vizing's theorem, Erdosde 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,
5color theorem, 3edgecoloring 3regular 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 ktuples
 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
References:
 Bollobas, Modern Graph Theory
 Diestel, Graph Theory
Back to Top
Combinatorial Optimization
 Matchings, bmatchings, Tjoins
 Matroids, matroid intersection, polymatroids
 Branchings and disjoint branchings
 Directed cuts, LucchesiYounger, EdmondsGiles
 Stable sets, stableset polyhedra
 Multiflows, the theorem of OkamuraSeymour
 Hypergraphs, clutters
Reference:
 A. Schrijver, Combinatorial Optimization, Wiley, 2003
Back to Top
Theory of Linear Inequalities
 Linear diophantine equations
 Linear proramming duality, Farkas' lemma
 Structure and complexity of polyhedra
 Blocking and antiblocking polyhedra
 Integer polyhedra
 Hilbert bases and total dual integrality
 Cutting plane proofs and Chvatal cuts
Reference:
 Schrijver, Theory of Linear and Integer Programming, pages 1244,
309359.
Back to Top
Probabilistic Methods in Combinatorics

Random Variables:
 Expectation, Variance, Conditional Expectation, Conditional Variance
 Convergence of random variables
 Laws of large numbers:
 Weak and Strong Laws, BorelCantelli Lemmas,
Kolmogorov's zeroone law
 Central limit theorem:
 Characteristic functions, Moment generating functions,
Joint Normal Distribution
 The Central limit theorem
 Martingales:
 Doob's Martingale, AzumaHoeffding Inequality, Optional stopping theorem
 Combinatorial Probability:
 First and Second Moment Methods, Deletion Method, The local lemma
 Random Graphs:
 Models, Thresholds and appearance of subgraphs
 Perfect matchings, independence number, chromatic number
References:
 Grimmett and Stirzaker, Probability and Random Processes,
(3rd ed.) Oxford University Press, 2011 [first three topics]
 AlonSpencer, The Probabilistic Method (3rd ed.) [next three topics]
 Janson, Luczak, and Rucinski, Random Graphs [last topic]
Back to Top
. . . . . . . . . . . . . . 
This page is maintained by the
ACO Webmaster,
at the
School of Mathematics,
Georgia Institute of Technology.
Last modified: September 30, 2013
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 nonGeorgia 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.

