**CS466/666: Algorithm Design and Analysis**

This is an advanced undergraduate / introductory graduate course on algorithm design for students in computer science, engineering, or mathematics.

Lecture: | Mondays and Wednesdays, 10:00-11:20, MC 4042. |
---|---|

Instructor: | Lap Chi Lau |

Office hours: | Mondays and Wednesdays, 11:30-12:30, DC 3120. |

Tutors: | Alex Tung, Robert Wang. |

TA office hours: | Alex Tung, Fridays, 10-11, DC 3139. Robert Wang, Thursdays, 5-6, DC 3139.. |

Piazza page: | piazza.com/uwaterloo.ca/spring2022/cs466666 |

Course outline: | [pdf] |

We will study probabilistic techniques and linear algebraic techniques in algorithmic design.

**Randomized Algorithms**- Probabilistic tools have become indispensible in algorithm design.- Chernoff bounds, graph sparsification, dimension reduction.
- balls and bins, hashing, data streaming.
- polynomial identity testing, parallel matching, network coding.
- probabilistic methods, local lemma.
- random walks, Markov chain Monte Carlo.
**Spectral Analysis**- We will study how eigenvalues and eigenvectors can be used to design and analyze algorithms, from random walks to graph partitioning to solving linear equations.- spectral graph theory, mixing time.
- Cheeger's inequality, local graph partitioning.
- electrical networks, random walks.
- spectral sparsification.
- multiplicative update methods, maximum flow.

**References:** Notes will be provided. See my previous notes on CS 466 Spring 2020, CS 466 Spring 2019, CS 466 Spring 2018 to get a good idea of the topics to come. The following are two reference books.

- Probability and Computing, by Mitzenmacher and Upfal
- Spectral and Algebraic Graph Theory, by Dan Spielman