Weeks 1-2: Counting things and using python

• Generating functions: counting partitions, permutations, Catalan objects.
• Rational and D-finite generating functions.
• Linear recurrence relations.
• Experimental math: guessing formulae from data.
• Algorithmic complexity, big-oh notation.
• Python: basic flow control, functions, lists and dictionaries.

Homework 1: hw1.ipynb or hw1.html Homework 2: hw2.ipynb or hw2.html

Weeks 3-4: Spanning Trees and Perfect Matchings

• Terminology: connectedness, degree, matchings.
• Adjacency matrix: eigenvalues/vectors, cycle counting.
• Spanning trees, Wilson’s algorithm
• Laplacian: Matrix-tree and Cauchy-Binet theorems.
• Kasteleyn matrix and related theory.

Week 5: Domino Shuffling and Non-intersecting lattice paths.

Week 6: Midterm week; start of posets

• Midterm exam on Tuesday Nov 4, in class.

Week 7: Posets and topological sorting

Week 8: Random generation of combinatorial objects

Week 9: Thanksgiving week; start of markov chains

Week 10: Coupling from the past, simulated annealing.