**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: | Tuesdays and Thursdays, 10:30-12:00, online. |
---|---|

Instructor: | Lap Chi Lau |

Office hours: | Tuesdays and Thursdays, 1:00-2:00, online. |

Tutors: | Sheik Shameer Sheik Saleem, Kam Cheun (Alex) Tung, Ji Xin, Hong Zhou |

TA office hours: | |

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

Course outline: | [pdf] |

We will study modern techniques in algorithms design and analysis, including probabilistic techniques, linear algebraic techniques, and optimization techniques.

**Randomized Algorithms**- Probabilistic tools have become indispensible in algorithm design.- tail inequalities, graph sparsification, dimension reduction.
- balls and bins, hashing, data streaming.
- polynomial identity testing, parallel matching, network coding.
- probabilistic methods, local lemma.
**Spectral Analysis**- We will study how eigenvalues and eigenvectors can be used to design and analyze algorithms, from random walks to graph partitioning to graph sparsification.- spectral graph theory, Cheeger's inequality.
- random walks, mixing time.
- electrical networks, hitting time, spectral sparsification.
**Linear Programming**- A general and powerful approach for combinatorial optimization and approximation algorithms.- linear programming, iterative rounding.
- duality theorem, multiplicative update methods.

**References:** Notes will be provided. See my previous notes on Algorithm Design and Analysis to get a good idea of the topics to come. The following is a list of main references. See the project page for further references.

- Probability and Computing, by Mitzenmacher and Upfal
- Notes on Spectral Graph Theory by Dan Spielman.
- The Design of Approximation Algorithms, by Williamson and Shmoys