- Week 1: Counting things and using python
- Generating functions
- Linear recurrence relations with constant coefficients
- Enumeration:
- Various classes of partitions and permutations
- regular languages
- tree-type structures and Catalan objects
- Asymptotics: Partial Fractions / Singularity analysis
- Multivariate generating functions for analysis of run time
- Experimental math
- Guessing formulae from data; fitting polynomial/rational/exponential functions
- Python
- basic flow control (if/then/else, loops, functions)
- Lists, dictionaries
- Week 2: Complexity and more programming skills
- Famous algorithms from undergraduate mathematics
- Matrix multiplication (naive, fast)
- Number theory: fast modular arithmetic, Euclidean algorithm
- Graph algorithms:
- breadth first/depth first search
- topological sort
- Strongly connected components
- Shortest path algorithms (all-pairs, single source, etc)
- Algorithm run-time analysis
- Sorting algorithms: insertion/selection sort, merge sort, quicksort, heap sort
- Recursion, dynamic programming, memoization
- Weeks 3-5: Graph theory
- Terminology: connectedness, degree, matchings
- Adjacency matrix
- Power method for largest/smallest eigenvalue
- Cycle counting
- Cheeger constant, expansion properties
- Laplacian
- Incidence matrix
- Matrix tree theorem / Cauchy-Binet theorem
- Laplacian eigenmaps (for visualization);
- Discrete harmonic functions, maximum principle
- Relation to random walk
- Random graphs
- Erdos-Renyi:
- Emergence of giant component (phase transition)
- Poisson approximation for number of cycles
- Random graphs are almost always expanders
- Sampling graphs from a given degree distribution
- Weeks 6-8: Statistical mechanics
- Terminology: energy, entropy, free energy, Hamiltonian formulation, phase transition
- Random spanning tree
- resistance networks, squared rectangles, random walk, planar green’s function
- Dimer model
- Kasteleyn matrix, kasteleyn orientation, edge placement probabilities
- Height function, plane partitions
- Determinant evaluations
- Ising model
- One dimensional exact solution
- Fisher lattice
- Sampling
- Markov chain monte carlo / metropolis algorithm
- Coupling from the past
- Simulated annealing
- Weeks 9-10: Optimization
- Combinatorial optimization
- Complexity classes; approximate solutions
- Revisit graph algorithms
- max flow / min cut
- Linear programming
- Standard terminology
- Simplex method
- duality
- Semidefinite programming
- Sum-of-squares certification of positivity
- Ising/quantum computing
- Adiabatic quantum computers (D-Wave)
- Actual annealing
- Simulated bifurcation algorithm