Lecture Notes

Additive combinatorics (Caltech 2016).

• ​Chapter 0: Preliminaries (asymptotics and groups)

• Chapter 1: Small doubling (sum sets)

• Chapter 2: The sum-product problem

• Chapter 3: The Balog-Szemeredi-Gowers Theorem

• Chapter 4: Arithmetic Progressions in Dense Sets

• Chapter 5: Quasi-polynomial Freiman–Ruzsa

• Chapter 6: Third Moment Energy

​​

Discrete Mathematics (Caltech 2014-2017).

• Lecture 1: Introduction to cryptography

• Lecture 2: Congruences

• Lecture 3: The RSA algorithm

• Lecture 4: Primality testing

• Lecture 5: Basic counting

• Lecture 6: Introduction to Graphs

• Lecture 7: More BFS

• Lecture 8: Eulerian cycles

• Lecture 9: Graph coloring

• Lecture 10: Spanning trees

• Lecture 11: Matchings

• Lecture 12: More matchings

• Lecture 13: Network flow

• Lecture 14: Flow exercises

• Lecture 15: Flow and bipartite graphs

• Lecture 16: Permutations

• Lecture 17: More permutations

• Lecture 18: Groups

• Lecture 19: Isomorphisms

• Lecture 20: Orbits and stabilizers

• Lecture 21: Counting and permutations

• Lecture 22: Power series

• Lecture 23: Generating functions

• Lecture 24: More generating functions

• Lecture 25: Partitions

• Lecture 26: More partitions

• Lecture 27: Shortest paths

​​

Graph theory (Caltech 2015-2017).

• Lecture 1: Recap (of above Discrete Math)

• Lecture 2: Matchings in bipartite graphs

• Lecture 3: Stable matchings

• Lecture 4: Matchings in general graphs

• Lecture 5: Graph connectivity

• Lecture 6: More graph connectivity

• Lecture 7: Minors

• Lecture 8: Planar and plane graphs

• Lecture 9: Euler's formula

• Lecture 10: Kuratowski's Theorem

• Lecture 11: Kuratowski and Coloring

• Lecture 12: Ramsey theory

• Lecture 13: More Ramsey theory

• Lecture 14: The probabilistic method

• Lecture 15: More probabilistic method

• Lecture 16: Crossing numbers

• Lecture 17: Extremal graph theory

• Lecture 18: More extremal graph theory

• Lecture 19: Graphs and matrices

• Lecture 20: Spectral graph theory

• Lecture 21: More spectral graph theory

• Lecture 22: Eigenvalues in regular graphs

• Lecture 23: Expanders

• Lecture 24: Error correcting codes

• Lecture 25: More error correcting codes

• Lecture 26: Art galleries and politicians

​​​​

Data Structures and Algorithms (Baruch 2024).

• Chapter 1: What is this course about?​

• Chapter 2: Running time (+ binary search)

• Chapter 3: Sorting

• Chapter 4: Graphs and BFS

• Chapter 5: First data structures (queue, stack, linked list)

• Chapter 6: Hash tables

• Chapter 7: Minimum spanning trees

• Chapter 8: Heaps

• Chapter 9: Dynamic programming

• Chapter 10: Greedy algorithms

• Chapter 11: Lightest paths

• Extra 1: Matchings

• Extra 2: Network flow

• Extra 3: Error correcting codes​

​​

​​​​