**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 4045. |
---|---|

Instructor: | Lap Chi Lau |

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

Tutors: | Pak Hay Chan, Akshay Ramachandran, Kaiyu Wu. |

TA office hours: | Pay Hay Chan, Thursdays, 2-3, DC 3129. Akhsay Ramachandran, Fridays, 1-2, DC 3128. |

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

Course outline: | [pdf] |

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

**Randomized Algorithms**- Probabilistic tools have become indispensible in algorithm design.- Chernoff bounds, graph sparsification.
- 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, Laplacian solver.
**Linear Programming**- A general and powerful approach for combinatorial optimization and approximation algorithms.- linear programming, iterative rounding.
- duality theorems, primal-dual methods.
- multiplicative update methods, maximum flow.

**References:** Notes will be provided. See my previous notes on Graduate Algorithms to get a good idea of the topics to come. The following is a list of main references. See my previous 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