Click on each subject to display syllabi.
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, Perron-Frobenius theorem. Markov chains and stochastic matrices. M-matrices
- 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 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
Reference
- Abstract Algebra by Dummit and Foote
Introduction to Graduate Algorithms
- Computability theory:
- Multi-tape Turing machines definitions; assume without covering simulations of multi-tape and other variants. (Sipser sections 3.1, 3.2)
- Non-deterministic 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:
- NP-Completeness: Definition of NP in terms of verification machines (Sipser section 7.3); NP-Completeness, polynomial-time reducibility; Cook/Levin theorem and its proof. (Sipser section 7.4)
- Reductions from satisfiability: 3cnfsat, clique, vertex cover, Hamiltonian path, 3-coloring, subset sum. (Sipser section 7.5)
- Decision versus computation: self-reducibility. (Sipser problem 7.36)
- BPP, amplification of acceptance probability. Polynomial identity testing, read-once 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, PSPACE-Completeness. (Sipser Chapter 8)
- Polynomial Hierarchy, time/space hieararchies
- Algorithms:
- Dynamic programming: Sequence alignment, Bellman-ford shortest path algorithm, finding negative cycles, Floyd-Warshall algorithm
- Minimum spanning trees and Shortest paths with advanced data structures such as Fibonacci heaps and Union-find data structures
- Max-flow: Ford-Fulkerson algorithm, max-flow min-cut theorem, Edmonds-Karp algorithm, scaling algorithm
- Matching: reduction from bipartite matching to network flow. Hopcroft-Karp 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
Design and Analysis of Algorithms
- Concentration Inequalities: Markov, Chebyshev, Chernoff, and McDiarmid
- LP Duality: Yao’s minimax principle, Primal-dual, Multiplicative-Weights for LPs/SDPs
- Convex Optimization: Gradient Descent, Ellipsoid/Cutting-plane Algorithms, SDPs
- Randomized Algorithms: Load Balancing, Min Cut, Online Matching, Packing LPs/IPs, Max Cut
- One of the following:
Approximation Algorithms: Steiner Tree, TSP, Vertex Cover/Set Cover, Competitive Ratio, Submodular Optimization, Price of Anarchy
or
Sampling Algorithms: Markov Chain Monte Carlo methods, coupling, conductance, mixing, applications.
References
- Randomized Algorithms by Motwani and Raghavan
- Approximation Algorithms by Vijay Vazirani
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
Combinatorial Optimization
- Matchings, b-matchings, T-joins
- Matroids, matroid intersection, polymatroids
- Branchings and disjoint branchings
- Directed cuts, Lucchesi-Younger, Edmonds-Giles
- Stable sets, stable-set polyhedra
- Multi-flows, the theorem of Okamura-Seymour
- Hypergraphs, clutters
Reference
- A. Schrijver, Combinatorial Optimization, Wiley, 2003
Theory of Linear Inequalities
- 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
Reference
- Schrijver, Theory of Linear and Integer Programming, pages 1-244, 309-359.
Probabilistic Methods in Combinatorics
- Random Variables:
- Expectation, Variance, Conditional Expectation, Conditional Variance
- Convergence of random variables
- Laws of large numbers:
- Weak and Strong Laws, Borel-Cantelli Lemmas, Kolmogorov''s zero-one law
- Central limit theorem:
- Characteristic functions, Moment generating functions, Joint Normal Distribution
- The Central limit theorem
- Martingales:
- Doob's Martingale, Azuma-Hoeffding 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]
- Alon-Spencer, The Probabilistic Method (3rd ed.) [next three topics]
- Janson, Luczak, and Rucinski, Random Graphs [last topic]
