TTIC 31150/CMSC 31150 - Mathematical Toolkit (Fall 2024)
Lectures: Mon/Wed 3:00-4:20 in TTIC 530
Discussion: Fri 3:00-3:50 in TTIC 529
Instructor: Avrim Blum
(Office hours: Fri 2:00-2:50 in TTIC 439)
TAs: Melissa Dutz (Office hours: Mon 1:30-2:20 in TTIC 506) and Donya Saless (Office hours: Wed 12:30-1:20 in TTIC 412.22)
Course description:
The course is aimed at first-year graduate students and advanced undergraduates, and focuses mostly on abstract linear algebra and probabilistic reasoning.
We intend to cover the following topics and examples:
- Abstract linear algebra: vector spaces, linear transformations, Hilbert spaces, inner product, Gram-Schmidt orthogonalization, eigenvalues and eigenvectors, Singular Value Decomposition, SVD applications.
- Discrete probability: events and random variables, Markov, Chebyshev and Chernoff-Hoeffding bounds. Balls and bins problems. Threshold phenomena in random graphs.
- Randomized algorithms (e.g., polynomial identity testing, perfect matchings, low-congestion routing).
- Gaussian variables, concentration inequalities, dimension reduction.
- Additional topics (to be chosen from based on time and interest): Martingales, Markov Chains, Random Matrices.
Coursework: The course will have 5 homeworks (60 percent), a midterm (15 percent) and a final (25 percent).
There is no textbook for this course. Please see the "Recommended test/readings" section below for some useful references.
Homeworks
Lecture Notes
- 09/30: Fields and vector spaces. Linear independence and bases. (slides)
- 10/02: Vector space applications and linear transformations. (slides) (discussion session 1)
- 10/07: Eigenvalues and eigenvectors, inner products. (slides)
- 10/09: Orthogonality and adjoints. (slides) [Hwk1 due] (discussion session 2)
- 10/14: The Real Spectral Theorem. (slides)
- 10/16: Singular Value Decomposition. (slides)
- 10/21: SVD for Matrices. (slides)
- 10/23: SVD applications. (slides) [Hwk2 due]
10/28: Midterm. You may bring in one sheet of notes.
- 10/30: Probability basics. (slides)
- 11/04: Probabilistic reasoning. (slides)
- 11/06: Tail inequalities 1. (slides) [Hwk3 due]
- 11/11: Tail inequalities 2. (slides)
11/13: [No class today]
- 11/18: Randomized routing. Randomized complexity classes. (slides)
- 11/20: Probability over uncountably-infinite spaces, Gaussian RVs, Johnson-Lindenstrauss Lemma. (slides) [Hwk4 due]
- 12/02: Random walks on graphs: commute time, cover time and electrical networks. (slides)
- 12/04: Markov chains and rapid mixing. (slides) [Hwk5 due]
Recommended texts/readings: