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 4:00-4: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
- Homework 1.
Due October 9. Hand in electronically using the following dropbox link. Please include your email address in your handin.
Lecture Notes
- 09/30: Fields and vector spaces. Linear independence and bases. (slides)
- 10/02: Vector space applications and linear transformations. (slides)
- 10/07: Eigenvalues and eigenvectors, inner products. (slides)
- 10/09: Orthogonality and adjoints. [Hwk1 due]
- 10/14: The Real Spectral Theorem.
- 10/16: Singular Value Decomposition.
- 10/21: SVD for Matrices.
- 10/23: SVD applications. [Hwk2 due]
10/28: Midterm. You may bring in one sheet of notes.
- 10/30: Probability basics.
- 11/04: Probabilistic reasoning.
- 11/06: Tail inequalities 1. [Hwk3 due]
- 11/11: Tail inequalities 2.
- 11/13: [No class today]
- 11/18: Randomized routing. Randomized complexity classes.
- 11/20: Probability over uncountably-infinite spaces, Gaussian RVs, Johnson-Lindenstrauss Lemma. [Hwk4 due]
- 12/02: Properties of the unit ball and Gaussian distribution in high-dimensional space.
- 12/04: Random walks on graphs: commute time, cover time and electrical networks. [Hwk5 due]
- Possible alternative topic: Markov chains and rapid mixing.
Recommended texts/readings: