15-750: Algorithms in the Real World, Spring 2023

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(\log n)$ time in the worst-case?
  • Optional: Lecture notes from 15-451 on shortest-path algorithms.
  • Optional: Kevin Wayne's original slides on binary 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)