CMU Graduate Algorithms, Spring 2021 (original) (raw)

Lecturers: Anupam Gupta (anupamg@cs), Rashmi Vinayak (rvinayak@cs).

TAs: Michael Rudow (mrudow@cs), Sandeep Pallerla (spallerl@cs).

Office hours: Please refer to the class calendar below.

Staff Email List: 15750-spring21-instructors at lists dot andrew dit cmu dah edu (Please use this email list for contacting the instructors instead of individual email addresses.)

Location: Online (zoom), Tue/Thu 10:40-noon. (Link to be shared on piazza.)

Piazza: http://piazza.com/cmu/spring2021/15750/home

Gradescope: https://www.gradescope.com/

Course Details and Policies

• Please read the course policies carefully!!!.
• Here are the course intro slides from lecture #1
• Links to resources to help brush up on your background.
• Here is a tentative schedule for the course.

Homeworks

• Homework 0 (due Monday, Feb 8), solutions (CMU only)
• Homework 1 (due Thursday, Feb 25), solutions (CMU only)
• Homework 2 (due Thursday, March 11), solutions (CMU only)
• Homework 3 (due Thursday, Apr 1), solutions (CMU only)
• Homework 4 (due Sunday, Apr 18), solutions (CMU only)
• Homework 5 (due Thursday, May 6), solutions (CMU only)

Lectures

• Lecture 1 (Feb 2). Introduction + Strassen's Algorithm (notes, older handwritten notes, board, intro slides)
  * Handout on big-O and recurrences from 15-451/651.
  * Chapter 1 from Kozen (WebISO access only).
  * Optional: Strassen's paper, some intuition for his formulas (1,2,3), CACM article on low-communication MatMult (and video)

• Lecture 2 (Feb 4). Minimum Spanning Trees and Amortized Analysis (handwritten notes, board, slides)
  * Scan of section on Kruskal and MSTs from Kleinberg/Tardos (WebISO access only).
  * Notes on the union-find data structures, both the list-based one we did in lecture, and the tree-based one we described but did not prove.
  I find this proof more accessible than Kozen's proof, try it and see what you think.
  * Basic animations of Kruskal/Prim's algorithms
  * Optional: Wayne's slides on the tree-based data structures, and a proof that any (reasonable) union-find data structure takes inverse Ackermann-time.
  * Optional: Kozen's chapters 2, 3 on MST and a generalization called Matroids, and the chapter on Union-find.

• Lecture 3 (Feb 9). Amortization (contd.) Shortest Paths and Heaps. (amortization notes, handwritten notes, board, slides for dijkstra, heaps)
  * Chapter from Kozen on Dijkstra, binomial heaps.
  * Kevin Wayne's original slides onbinary and binomial heaps and (optional) Fibonacci heaps.

• Lecture 4 (Feb 11). Dynamic Programming. (board)
  * Lecture notes (and a recitation worksheet) from the 15-451 course, discussing several problems, via memoization and table-filling.
  * Some notes for the Talk Scheduling (aka Max-Weight Interval Packing) problem.
  * Kleinberg-Tardos has many fun examples of solving problems using DP (see the slides1, slides2 by Kevin Wayne).

• Lecture 5 (Feb 16). Hashing 1. (board, notes in the form of slides with some handwritten content)
  * Lecture notes on hashing from last year's 15-750.

• Lecture 6 (Feb 18). Hashing 2. (board, notes in the form of slides with some handwritten content)
  * Lecture notes on hashing from last year's 15-750 (same as the one linked above).

• Lecture 7 (Feb 25). Hashing 3: k-wise Independence, Cuckoo Hashing, Bloom Filters. (board, notes in the form of slides with some handwritten content)
  * Lecture notes on hashing from last year's 15-750 (same as the one linked above).

• Lecture 8 (Mar 2). Hashing 4: Bloom Filters, Load Balancing, Chernoff Bounds. (board, notes in the form of slides with some handwritten content)
  * Lecture notes on load-balancing and Chernoff bounds from last year's 15-750.
  * A couple of detailed examples/exercises on Chernoff bounds.

• Lecture 9 (Mar 4). Hashing 5: Two Choices, the Data Streaming Model. (board, notes in the form of slides with some handwritten content)
  * Lecture notes on streaming.

• Lecture 10 (Mar 9). Hashing 6: Locality Sensitive Hashing and Near-Neighbor Search (notes, board)
  * Chapter on LSH/NN search from the MMDS book (you can skip Section 3.8 onwards).
  * CACM technical perspective on LSH/NN search by Chazelle, and technical review (author copy) by Andoni and Indyk.

• Lecture 11 (Mar 11). Optimization I: Flows and Matchings. (preliminary notes, handwritten notes I and II, board)
  * Notes and worksheet (sols) for Max-Flows from our 15-451 course.
  * Part of the chapter from the Kleinberg-Tardos book.
  * Animations of some basic max-flow algorithms (Ford-Fulkerson, Edmonds-Karp, Dinics)

• Lecture 12 (Mar 18). Optimization II: Flows (finish), Linear Programming (introduction). (handwritten notes, board)
  * Understanding and Using Linear Programming by Matousek/Gaertner is excellent (free from CMU). Chapters:Introduction, Examples, LP Basics.
  * The online LP solver we used: it's useful to play with, especially if you haven't seen LPs before.
  * More serious solvers: CVXOPT and PuLP: Solving linear/convex optimization problems in Python. Free LP solver from COIN-OR. Commercial ones from Gurobi and CPlex.

• Lecture 13 (Mar 23). Optimization III: Linear Programming (applications). (handwritten notes, board)
  * Understanding and Using Linear Programming by Matousek/Gaertner is excellent (free from CMU). Chapters:Introduction, Examples, LP Basics.

• Lecture 14 (Mar 25). LP wrapup. NP Hardness and Limits of Efficient Algorithms. (handwritten notes, board)
  * Notes from 15-451, and worksheet.

• Lecture 15 (Mar 30). Combating Intractability (notes, board)
  * The Williamson-Shmoys book on Approximation algorithms is an excellent source.
  * Karp's original paper, and a more recent list of hard problems.

• Lecture 16 (Apr 1). Online Decision Making I: Online Algorithms and Competitive Analysis (online algos notes from 15-451, board)

• Lecture 17 (Apr 6). Online Decision Making II: The Experts Problem and the Multiplicative Weights Framework (handwritten notes, some slides, board)
  * Slides by Avrim Blum.
  * Notes from our 15-859 course.

• Lecture 18 (Apr 8). Online Decision III and Optimization IV: The Gradient Descent Framework (handwritten notes)
  * Notes from 15-451.
  * Optional: Potential function proofs of first-order methods by Nikhil Bansal and myself.

• Lecture 19 (Apr 13). Dimension Reduction 1: Preserving Pairwise Distances (JL Transform) (board, notes in the form of slides with some handwritten content)
  * SciKit's random projection implementation.
  * Lecture notes on JL Transform from 15-853 Fall 2015 course.
  * (Optional) Proofs of Johnson-Lindenstrauss: Indyk/Motwani, Dasgupta/Gupta, Achlioptas.
  * (Optional) Fast JL transforms: Ailon-Chazelle Ailon-Liberty.

• Lecture 20 (Apr 20). Dimension Reduction 2: JL continued, Principal Component Analysis and Singular Values (board, notes in the form of slides with some handwritten content)
  * Chapter 11 (and slides) from the MMDS book about PCA, SVD, etc.
  * Chapter 3 from the Blum-Hopcroft-Kannan book.

• Lecture 21 (Apr 22). Dimension Reduction 3: PCA & SVD continued; Algorithms for Coding 1 (board, notes in the form of slides with some handwritten content)
  * (Same as above lecture) Chapter 11 (and slides) from the MMDS book about PCA, SVD, etc, and Chapter 3 from the Blum-Hopcroft-Kannan book.
  * Scribe notes from 15-853 ("Algorithms in the real world") Fall 2019 course.

• Lecture 22 (Apr 27). Algorithms for Coding 2 (Slides, board (used intermittently throughout the lecture))
  * Scribe notes from 15-853 ("Algorithms in the real world") Fall 2019 course.

• Lecture 23 (Apr 29). Algorithms for Coding 3 (Slides, board (used intermittently throughout the lecture))
  * Scribe notes from 15-853 ("Algorithms in the real world") Fall 2019 course (only some parts are relevant to what we covered in the lecture).
  * Lecture notes on basic concepts on polynomials and Reed-Solomon codes from Spring 2019 15-451/651.

• Lecture 24 (May 4). Compression (Slides, board (used intermittently throughout the lecture))
  * Guy Blelloch's notes on compression. Chapters 1, 2 and 3 are relevant to what was covered in the lecture.
  * (Optional) Shannon's 1948 paper.

• Lecture 25 (May 6). Compression 2 and Course Review (Slides on Compression 2 and the review of the Hashing module)

Maintained by Anupam Gupta and Rashmi Vinayak.