<Plain-Text Page>  Requirements for the ACO Comprehensive Examination  
ACO Program
ACO Home Page
 
Admission Information
Program Description
- Organization
- Academic Requirements
- Schedule of Classes
- Core Courses
- Additional Courses
- Typical Program of Study
- Comprehensive Examination
- Requirements for Compreh. Exam.
Comb. Methods
Algorithms
Graphs
Comp. Complexity
LP and IP
Convexity
Algebra
Topology
Probability
- Minor Field of Study
- The Dissertation
Affiliated Faculty
Students
Alumni
Research Program
ACO News
ACO Events
ACO Internal
 
Georgia Tech
College of Computing
School of Ind. Sys. Eng.
School of Mathematics
School of Electrical Eng.
 
Help
Advanced Search
 
Contact WEBmaster
 
 
 
Georgia Institute of Technology


Requirements for the ACO Comprehensive Examination

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


Combinatorial Methods

- 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.

References

  1. E. Bender and S.G. Williamson, Foundations of Applied Combinatorics, Addison-Wesley, 1991.
  2. L. Lovasz, Combinatorial Problems and Exercises, North-Holland, 1979.
  3. H. Wilf, Generatingfunctionology, Academic Press, 1990.


Design and Analysis of Algorithms

- 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.

References

  1. T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms, McGraw-Hill, 1990.
  2. A. Aho, J. Hopcroft, and J. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.


Graphs and Graph Algorithms

- 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.


* = without proof

References

  1. B. Bollobas, Graph Theory - An Introductory Course, Springer-Verlag, 1979.


Computational Complexity Theory

- 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.

References

  1. J. Balcazar, J. Diaz, and J. Gabarro, Structural Complexity, vol. I and II, Springer-Verlag, 1988.
  2. J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.


Linear Programming and Integer Programming

- Formulations

- Primal, dual and revised simplex algorithms

- Duality and sensitivity analysis

- Degeneracy

- 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

References

  1. V. Chvatal, Linear Programming, W.H. Freeman, 1983.
  2. G. Nemhauser and L. Wolsey, Integer and Combinatorial Optimization John Wiley & Sons, 1988.


Convexity

- 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.

References

  1. R. Rockafellar, Convex analysis, Princeton Univ. Press, 1970.
  2. A. Brondsted, An Introduction to Convex Polytopes, Springer-Verlag, 1983.
  3. P. McMullen and G. C. Shephard, Convex Polytopes and the Upper Bound Conjecture, Cambridge Univ. Press, 1971.


Algebra

- 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.

References

  1. R. Dean, Classical Abstract Algebra, Harper & Row, 1990.
  2. M. Artin, Algebra, Prentice-Hall, 1991.


Topology/Linear Algebra

- 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.

References

  1. R. Kasriel, Undergraduate Topology, W. Saunders, 1971 (reprinted by R. Krieger).
  2. A. Taylor, Introduction to Functional Analysis, John Wiley & Sons, 1958.
  3. G. Cain, Introduction to General Topology, Addison-Wesley, 1992.
  4. B. Bollobas, Linear analysis : an introductory course, Cambridge Univ. Press, 1990.


Probability

- 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.

References

  1. W. Feller, An introduction to probability theory and its applications, vol. I and II, John Wiley & Sons, 1957.
  2. J. Lamperti, Probability; a survey of the mathematical theory, 2nd. ed. John Wiley & Sons, 1996.


 <Plain-Text Page (ACO Program Web Pages)  

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

[Viewable With Any Browser] [Georgia Tech] [Write us]

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

Last modified: October 30, 2011


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.