CMS 139 Design and Analysis of Algorithms

Term: Winter 2020 Lectures: MW 10:30-11:55, 213 ANB
Instructor: Thomas Vidick (vidick@caltech.edu). Office Hours: Tuesday 1:30-2: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 undergraduate-level 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 12-unit 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 4-6 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 no-collaboration.

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 write-up 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 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.

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
    • Median-finding
  • 01/08 Lecture 2: Flows
    • Ford-Fulkerson
    • Karger’s min-cut algorithm
    • HW1 due Friday
  • 01/13 Lecture 3: Randomized algorithms
    • The class BPP
    • Markov and Chebyshev inequality
    • Application: analysis of sampling-based algorithm for median-finding
  • 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 Johnson-Lindenstrauss lemma
    • Application: Approximate nearest neighbors using locality-sensitive 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
    • Midterm due Friday

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

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