## TTIC 31150/CMSC 31150 - Mathematical Toolkit (Spring 2021)

### Lectures: Tue/Thu 4:20-5:40pm, Online (See Canvas page for zoom link)

### Discussion: Wed 6:00-7:00, Online

### Instructor: Avrim Blum
(Office hours: Mon 1:00-2:00)

### TAs: Han Shao
(Office hours: Mon 6:00-7:00) and Tushant Mittal (Office hours: Wed 11:00-12:00)

**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, SVD.
- Discrete probability: random variables, Markov, Chebyshev and Chernoff-Hoeffding bounds.
- Gaussian variables, concentration inequalities, dimension reduction.
Spectral partitioning and clustering.
- Additional topics (to be chosen from based on time and interest): Martingales, Markov Chains, Random Matrices, Chaining Methods

**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/30: Fields and vector spaces. Linear independence and bases.
- 04/01: Vector space applications and linear transformations.
- 04/06: Eigenvalues and eigenvectors, inner products.
- 04/08: Orthogonality and adjoints.
- 04/13: The Real Spectral Theorem.
- 04/15: Singular Value Decomposition.
- 04/20: SVD for Matrices.
- 04/22: SVD applications.
- 04/27:
**Midterm**. You may refer to the lecture notes available on the class website and any handwritten notes of your own you wish to make in advance. See canvas site for full instructions.
- 04/29: Probability basics.
- 05/04: Probabilistic reasoning.
- 05/06: Tail inequalities 1.

**Recommended texts/readings:**