CMS 139 Design and Analysis of Algorithms

Term: Winter 2019
Lectures: MW 10:00-11:30, 213 ANB
Instructor: Thomas Vidick (vidick@cms.caltech.edu). Office Hours: Tuesday 5-6pm, 207 ANB
TAs: Spencer Gordon (slgordon@caltech.edu) and William Xu (wxu@caltech.edu). Office Hours: Wednesday 5-6pm, 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 undergraduate-level algorithms, please register for CS38 instead.

Evaluation

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.

Communication

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
  • HW 4 due Friday

• 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:

• Randomized algorithms: Probability and Computing by Mitzenmacher and Upfal and Randomized Algorithms by Motwani and Raghavan, and The Probabilistic Method.
• Approximation algorithms: Approximation Algorithms by Vazirani.
• Combinatorial optimization: Combinatorial optimization, polyhedra and efficiency, by Schrijver. See also the publicly available lecture notes by Schrijver.

Links to similar courses taught at other universities which have lecture notes online:

• Linear and Semidefinite Programming, Advanced Approximation Algorithms and A Theorist’s Toolkit, taught by Ryan O’Donnell at CMU.
• Combinatorial Algorithms and Data Structures, taught by Satish Rao at Berkeley.
• Mathematical Toolkit, taught by Madhur Tulsiani at TTI/University of Chicago.
• Advanced Algorithm Design, taught by Sanjeev Arora at Princeton.
• Randomized Algorithms and Probabilistic Analysis, taught by Greg Valiant at Stanford.

See also the following notes available online:

• Semidefinite Programs and Combinatorial Optimization, by Laslo Lovasz.