CMS 139 Design and Analysis of Algorithms
Term: Winter 2019
Lectures: MW 10:0011:30, 213 ANB
Instructor: Thomas Vidick (vidick@cms.caltech.edu). Office Hours: Tuesday 56pm, 207 ANB
TAs: Spencer Gordon (slgordon@caltech.edu) and William Xu (wxu@caltech.edu). Office Hours: Wednesday 56pm, 205 ANB.
Course description
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 undergraduatelevel algorithms, please register for CS38 instead.
Evaluation
This is a 12unit 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 warmup 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 takehome final with a oneweek 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.
Communication
We will use Piazza for all classrelated 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 samplingbased algorithm for medianfinding
 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 JohnsonLindenstrauss lemma
 Application: Approximate nearest neighbors using localitysensitive 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
Resources
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: