CMU Algorithms in the Real World, Spring 2023 (original) (raw)

Lecturer: Ryan O'Donnell (odonnell@cs).

TAs: Liyao Fu (liyaof@andrew), Emre Yolcu (eyolcu@cs), Billy Yan (yunzhouy@andrew).

Office hours:

• Mon. 3pm--4pm, with Billy, on Zoom.
• Tue. 2:30--3:30, with Ryan, in Gates 7213.
• Wed. 6pm--7pm, with Liyao, on Zoom.
• Fri. 1pm--2pm, with Emre, on Zoom.

Contacting us: Please use private messages on Piazza instead of emailing the course staff; this helps messages to not get lost.

Location: Margaret Morrison A14, Tue/Thu 11:00-12:20.

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

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

Course Details and Policies

• Please read the course policies carefully!!!
• Links to resources to help brush up on your background.
• The course page will develop more as we proceed through the lectures.

Homeworks

• Homework 1 (due Tuesday, Feb. 7).
• Homework 2 (due Tuesday, Feb. 21).
• Homework 3 (due Tuesday, Mar. 14).
• Homework 4 (due Tuesday, Mar. 28).
• Homework 5 (due Tuesday, Apr. 11).
• Homework 6 (due Tuesday, Apr. 25).

Lectures

• Lecture 1 (Jan 17). Introduction + Strassen's Algorithm (notes, older handwritten notes).
  * Handout on big-O and recurrences from 15-451/651, and a video from 15-751.
  * 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 (Jan 19). Minimum Spanning Trees (notes, older handwritten notes)
  * Notes on the union-find data structures, both the list-based one we did in lecture, and (optional) the tree-based one we did not get to.
  * Basic animations of Kruskal/Prim's algorithms

• Lecture 3 (Jan 24). Amortization + Shortest Paths with Dijkstra (amortization notes, handwritten notes, some slides animating Dijkstra)
  * Animation of a (max) heap based priority queue data structure.
  Do you see how all operations take O(logn)O(\log n)O(logn) time in the worst-case?
  * Optional: Lecture notes from 15-451 on shortest-path algorithms.
  * Optional: Kevin Wayne's original slides onbinary and binomial heaps and Fibonacci heaps.

• Lecture 4 (Jan 26). Dynamic Programming. (My handwritten notes)
  * Lecture notes (and a recitation worksheet) from the 15-451 course, discussing several problems, via memoization and table-filling.
  * Notes for small-space implementation of LCS.
  * Kleinberg-Tardos has many fun examples of solving problems using DP (see the slides1, slides2 by Kevin Wayne).

• Lecture 5 (Jan 31). Hashing 1, with SUHA. (My handwritten notes)
  * Some notes on hashing.

• Lecture 6 (Feb 2). Hashing 2: Max load, power of 2 choices, Bloom filters. (My handwritten notes)

• Lecture 7 (Feb 7). Hashing 3: Universal hashing. (My handwritten notes)

• Lecture 8 (Feb 9). Hashing 4: Implementing universal hashing, and perfect hashing. (My handwritten notes)

• Lecture 9 (Feb 14). Dimensionality Reduction with the JL Lemma (My handwritten notes) * SciKit's random projection implementation. * Lecture notes on JL Transform from a previous year. * (Optional) Proofs of Johnson-Lindenstrauss: Indyk/Motwani, Dasgupta/Gupta, Achlioptas. * (Optional) Fast JL transforms: Ailon-Chazelle,Ailon-Liberty.

• Lecture 10 (Feb 16). Symmetric matrices: finding eigenvalues and eigenvectors (My handwritten notes)

• Lecture 11 (Feb 21). Principal Component Analysis (PCA) (My handwritten notes) * Chapter 11 (and slides) from the MMDS book about PCA, SVD, etc. * (Optional) Chapter 3 from the Blum-Hopcroft-Kannan book.

• Lecture 12 (Feb 23). Max-st-Flow and Min-st-Cut (My handwritten notes)
  * Notes and recitation worksheet 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 13 (Mar 14). Optimization: From Max-Flow to LP (My handwritten notes)
  * Notes about LPs from our 15-451 course.
  * Understanding and Using Linear Programming by Matousek/Gaertner is excellent (free from CMU). Chapters:Introduction, Examples, LP Basics.
  * An online LP solver: 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 14 (Mar 16). How to solve Linear Programs (My handwritten notes)

• Lecture 15 (Mar 21). Solving LPs with a separation oracle: Directed MST (My handwritten notes)
  * Video

• Lecture 16 (Mar 23). Rounding ILPs to LPs.
  * Video 1
  * Video 2

• Lecture 17 (Mar 28). Online algorithms and decision making, Part 1 (My handwritten notes)
  * online algorithms notes from 15-451

• Lecture 18 (Mar 30). Online algorithms and decision making, Part 2 (My handwritten notes)

• Lecture 19 (Apr 4). Online learning and prediction, Part 1 (My handwritten notes)
  * Multiplicative weights notes from 15-859

• Lecture 20 (Apr 6). Online learning and prediction, Part 2 (My handwritten notes)

• Lecture 21 (Apr 11). Solving zero-sum games via online learning (My handwritten notes)

• Lecture 22 (Apr 18). Random walks on graphs I: Markov Chains (My handwritten notes)
  * First of three lectures in a sequence about spectral graph theory. Sorry the audio on this is low, but it gets higher.

• Lecture 23 (Apr 20). Random walks on graphs II: Undirected graphs (My handwritten notes)

• Lecture 24 (Apr 25). Spectral graph theory I (My handwritten notes)

• Lecture 25 (Apr 27). Spectral graph theory II (My handwritten notes)

Maintained by Ryan O'Donnell, based on course pages by Anupam Gupta and Rashmi Vinayak