CMS 139 Design and Analysis of Algorithms
Term: Winter 2019
Lectures: MW 10:00-11:30, 213 ANB
Instructor: Thomas Vidick (firstname.lastname@example.org). Office Hours: Tuesday 5-6pm, 207 ANB
TAs: Spencer Gordon (email@example.com) and William Xu (firstname.lastname@example.org). Office Hours: Wednesday 5-6pm, 205 ANB.
This course develops core principles for the analysis and design of algorithms. Basic material includes mathematical techniques for analyzing performance in terms of resources, such as time, space, and randomness. The course introduces the major paradigms for algorithm design, including randomized algorithms, linear and semidefinite programming, approximation algorithms, spectral methods, and online learning.
Prerequisites: Ma 2, Ma 3, Ma/CS 6a, CS 21, CS 38/138, and CMS/ACM/EE 116 or ACM/CMS 113 or equivalent.
This should not be your first course in algorithms. If you have not previously taken undergraduate-level algorithms, please register for CS38 instead.
This is a 12-unit course. In addition to attending 3 hours of lecture weekly, students are expected to:
- (10% of grade) Prepare for lecture by completing from zero to two small exercises, to be turned in at the start of lecture. The exercise, if any, will always be indicated at the end of the previous lecture notes. These exercises are either a direct application of the previous lecture, or a simple warm-up towards the next lecture.
- (50% of grade) Turn in a (roughly) weekly homework set. There will be five such sets.
- (20% of grade) Turn in a midterm. This will be similar to a homework, except that collaboration is not allowed.
- (20% of grade) Complete the final. This is a take-home final with a one-week time limit, that has to be completed with no collaboration. It is similar to the midterm, except that it will cover material from the entirety of the course.
See the detailed syllabus and the collaboration policy.
We will use Piazza for all class-related discussions. Please direct your questions and comments to the course website on piazza. (Contact the TAs if you do not have access to the website.) You are free to post anonymously. If posting about a homework, make sure your question does not reveal a partial solution, and post it publicly. If you need to, you can also post privately, but this is not the preferred option.
Homework submission will be handled via Gradescope.
Indicative schedule of lectures
- 01/07 Lecture 1: Randomized algorithms
- The complexity class BPP
- Events and random variables
- Markov and Chebyshev inequality
- Application: analysis of sampling-based algorithm for median-finding
- 01/09 Lecture 2: Chernoff bound
- Statement and proof
- Application: error amplification for BPP
- Application: randomized routing on the hypercube
- 01/14 Lecture 3: Linear programming & approximation algorithms
- Brief review of linear programming
- A linear programming relaxation for the uncapacitated facility location problem
- 01/16 Lecture 4: Uncapacitated facility location
- Dual linear program
- Deterministic rounding
- Randomized rounding
- HW1 due Friday
01/21 No lecture (Martin Luther King Day)
- 01/23 Lecture 5: Streaming algorithms
- The streaming model
- Approximating the first and second frequency moments
- Derandomization using pairwise independent hashing
- 01/28 Lecture 6: Dimension reduction
- The Johnson-Lindenstrauss lemma
- Application: Approximate nearest neighbors using locality-sensitive hashing
- 01/30 Lecture 7: Semidefinite programming
- Motivation: a relaxation for MAXCUT
- Semidefinite programs. Canonical form.
- Duality for SDP
- HW2 due Friday
- 02/04 Lecture 8: Rounding semidefinite programs
- A semidefinite relaxation for general quadratic programs
- Randomized rounding
- Deterministic rounding
02/06 Lecture 9: The ellipsoid algorithm
- 02/11 Lecture 10: Combinatorial optimization (1/2)
- Matchings, matroids
- Midterm due Monday
- 02/13 Lecture 11: Combinatorial optimization (2/2)
- Edmonds Blossom algorithm
02/18 No lecture (President’s Day)
- 02/20 Lecture 12: Online algorithms
- The multiplicative weights algorithm (MWA)
- Applications of MWA
- HW3 due Friday
- 02/25 Lecture 13: Spectral graph theory
- Matrices associated to a graph
- Cheeger’s inequality
- 02/27 Lecture 14: Spectral partitioning
03/04 Lecture 16: Markov Chains
03/06 Lecture 17: Approximate counting/volume estimation
- 03/11 Lecture 16: Solving systems of linear equations (1/2)
- Iterative solvers
- HW 5 due Monday
- 03/13 Lecture 18: Solving systems of linear equations (2/2)
- Laplacian solvers
- Final due Monday March 18
We won’t be following any particular textbooks. Lecture notes will be posted on piazza after each lecture. Specific portions of the course are covered in detail in the following textbooks:
Links to similar courses taught at other universities which have lecture notes online:
See also the following notes available online: