TTIC 31150/CMSC 31150 - Mathematical Toolkit (Spring 2023)
Lectures: Mon/Wed 1:30-2:50 in TTIC 530
Discussion: Fri 2:00-2:50 in TTIC 529
Instructors: Avrim Blum
(Office hours: Mon 3:00-4:00 in TTIC 439) and Ali Vakilian (Office hours: Wed 3:00-4:00 in TTIC 518)
TAs: Kshitij Patel (Office hours: Mon 4:30-5:30 in TTIC 512.18) and Xiao Luo (Office hours: Wed 4:30-5:30 in TTIC 412.14)
Course description:
The course is aimed at first-year graduate students and advanced undergraduates. The goal of the course is to collect and present important mathematical tools used in different areas of computer science. The course will mostly focus on linear algebra and probability. 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
- 03/20: Fields and vector spaces. Linear independence and bases. (slides)
- 03/22: Vector space applications and linear transformations. (slides)
- 03/27: Eigenvalues and eigenvectors, inner products. (slides)
- 03/29: Orthogonality and adjoints. (slides)
- 04/03: The Real Spectral Theorem. (slides)
- 04/05: Singular Value Decomposition. (slides)
- 04/10: SVD for Matrices. (slides)
- 04/12: SVD applications. (slides)
04/17: Midterm. You may bring in one sheet of notes.
- 04/19: Probability basics. (slides)
- 04/24: Probabilistic reasoning. (slides)
- 04/26: Tail inequalities 1. (slides)
- 05/01: Tail inequalities 2. (slides)
- 05/03: Randomized routing. Randomized complexity classes. (slides)
- 05/08: Probability over uncountably-infinite spaces, Gaussian RVs, Johnson-Lindenstrauss Lemma. (slides)
- 05/10: Properties of the unit ball in high-dimensional space. (slides)
- 05/15: Random walks on graphs: commute time, cover time and electrical networks. (slides)
- 05/17: Markov chains and rapid mixing. (slides)
Recommended texts/readings: