15-750: Graduate Algorithms, Spring 2021

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 on binary 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.