CMS 139 Design and Analysis of Algorithms
Term: Winter 2020
Lectures: MW 10:3011:55, 213 ANB
Instructor: Thomas Vidick (vidick@caltech.edu). Office Hours: Tuesday 1:302:30pm, 207 ANB
TA: Jing Ding (jding@caltech.edu). Office Hours: TBA, 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.
Office hours and recitation
You are strongly encouraged to come to my office hours or to those held by the TA. You can come to office hours to discuss assignments, but not only for that. You can come to discuss anything related to the course: the material covered in class, the material not covered in class, your interest in the class, etc. You are also welcome to come in for advice on how to do well in the class.
Recitation sections will be held (roughly) once every two weeks. The goal of recitation is to spend additional time reviewing key material from the class, or that is needed to understand class. Recitations are particularly useful for students having difficulties for the class, but they are meant for all students.
Resources
We won’t be following any particular textbook. Lecture notes will be posted on piazza after each lecture. Standard books you may find useful include Probability and Computing by Mitzenmacher and Upfal, Randomized Algorithms by Motwani and Raghavan, and Approximation Algorithms by Vazirani.
Evaluation
This is a 12unit course. In addition to attending 3 hours of lecture weekly, students are expected to:
 (10% of grade) At the end of the lecture notes from class on any given day there will (often, but not always) be one or two small exercises, to be handed in on paper at the start of the next class. The goal of the exercises is to make sure every student is following the class, and that no one falls behind; they are not meant to be difficult and should take under 20 minutes to complete. Grading of the exercises will be done generously, and skipping up to 20% of them will not affect your grade.
 (50% of grade) Turn in a (roughly) weekly homework set. Assignment consists of 46 exercises each. The assignment will be available on Piazza at least one week before the due date. Solutions are to be handed in via Gradescope (handwritten and scanned solutions are equally good as latexed solutions). Instructions for registering on Gradescope will be posted to Piazza in the first week. Grading will take into account clarity and rigor of exposition: make sure your solutions are presented appropriately and include complete proofs whenever required.
 (40% of grade) A midterm and a final, each worth 20% of the grade. The midterm and final are similar to the homeworks in length and difficulty, except that they cover material from the entire class to date. You have one week to solve each of them, and they are strictly nocollaboration.
Collaboration policy
 The exercises, the midterm, and the final, should be completed on your own: strictly no collaboration.
 The homeworks can be solved in collaboration with other students in the class (and I encourage it). But you should read and think about each problem alone for at least a few minutes
before collaborating. You must produce the final writeup
for submission alone, without relying on notes of any kind from your discussions; your solution
must depend solely on your own understanding.
 It is ok to look up definitions online or wherever you find convenient. It is not ok to use solutions found online, in whole or in part. If by accident you find a solution to an assigned problem, or a problem that is close to an assigned problem, you should immediately put it aside. Do not violate the honor code. In case of uncertainty ask.
In all cases where collaboration is allowed, you should indicate on your solution the name of your collaborator(s).
See 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.
Piazza questions about the Homeworks will only be answered up until 24 hours before the submission deadline. For the midterm and final, we will stop 48 hours before the deadline. After that, you’re on your own! In case you spot a typo or a mistake, clearly indicate it on your solution. Whenever possible, use best judgement to find the correct formulation for a question.
Homework submission will be handled via Gradescope.
Indicative schedule of lectures
 01/06 Lecture 1: Review
 Basics of algorithm analysis: Quicksort
 Events and random variables
 Randomized quicksort
 Medianfinding
 01/08 Lecture 2: Flows
 FordFulkerson
 Karger’s mincut algorithm
 HW1 due Friday
 01/13 Lecture 3: Randomized algorithms
 The class BPP
 Markov and Chebyshev inequality
 Application: analysis of samplingbased algorithm for medianfinding
 01/15 Lecture 4: The Chernoff bound
 Statement and proof
 Application: The class BPP. Error amplification
 Application: randomized routing on the hypercube

01/20 No lecture (Martin Luther King Day)
 01/22 Lecture 5: Linear programming & approximation algorithms
 Brief review of linear programming
 A linear programming relaxation for the uncapacitated facility location problem
 HW2 due Friday
 01/27 Lecture 6: Uncapacitated facility location
 Dual linear program
 Deterministic rounding
 Randomized rounding
 01/29 Lecture 7: Streaming algorithms
 The streaming model
 Approximating the first and second frequency moments
 Derandomization using pairwise independent hashing
 02/03 Lecture 8: Dimension reduction
 The JohnsonLindenstrauss lemma
 Application: Approximate nearest neighbors using localitysensitive hashing
 02/05 Lecture 9: Semidefinite programming
 Motivation: a relaxation for MAXCUT
 Semidefinite programs. Canonical form.
 Duality for SDP
 HW3 due Friday
 02/10 Lecture 10: Rounding semidefinite programs
 A semidefinite relaxation for general quadratic programs
 Randomized rounding
 Deterministic rounding
 02/12 Lecture 11: The ellipsoid algorithm

02/17 No lecture (President’s Day)
 02/19 Lecture 12: Online algorithms
 The multiplicative weights algorithm (MWA)
 Applications of MWA
 02/24 Lecture 13: Spectral graph theory
 Matrices associated to a graph
 Cheeger’s inequality
 02/26 Lecture 14: Spectral partitioning

03/02 Lecture 16: Markov Chains

03/04 Lecture 17: Approximate counting/volume estimation
 03/09 Lecture 16: Solving systems of linear equations (1/2)
 Iterative solvers
 HW 5 due Monday
 03/11 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: