Toolkit for Modern Algorithms

CSE 422 | Winter 2025

Course information

Instructor: Jerry Li, Office hours: 2-3pm Wed in CSE2 315
Teaching Assistants: Lukshya Ganjoo (OH: Tues 4:30-5:30 Allen 5th floor breakout), Jack Zhang (OH: Mon 2-3 CSE2 152)
Location: CSE2 G01
Times: Tu, Th 11:30 - 12:50
Canvas
Gradescope

Course description

This course provides a rigorous introduction to the principles of modern algorithm design, with a particular focus on the analysis of large, noisy data sets, and the algorithmic principles underlying modern statistics and machine learning. For most topics, there will be an associated assignment, where students will get their hands dirty, experimenting with underlying ideas. Evaluation is based on nine weekly assignments. No late assignments are allowed, but your lowest score will be dropped.

Prerequisites

The formal requirements are CSE 311 and 312 (or equivalent background).

This should be considered an advanced undergraduate course. Students should be comfortable with data structures, probability theory, and linear algebra.

Tentative course schedule and topics†

Click on each lecture to see additional (optional) reading for the associated lecture.

Week 1: Modern Hashing

Lecture 1 (1/7): Course introduction. Consistent hashing. [notes] [scribe notes]
- Akamai paper: Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web (STOC 1997)
- A survey of Algorithmic Nuggets in Content Delivery
- Chord: A scalable peer-to-peer lookup service for internet applications (SIGCOMM 2001)
- Dynamo: Amazon’s highly available key-value store (SOSP 2007)
- Rendezvous hashing: A name-based mapping scheme for Rendezvous (Nov, 1996)
Lecture 2 (1/9): Heavy hitters, count-min sketch. [notes] [scribe notes]
- Network applications of Bloom filters: A survey (Broder and Mitzenmacher, 2005)
- An improved data stream summary: The count-min sketch and its applications (Cormode and Muthukrishnan, 2003)
- Formal analysis of balls in bins (A. Gupta, CMU)

Week 2: Metric data

Lecture 3 (1/14): Similarity search [notes] [scribe notes]
- k-d trees on Wikipedia
- Python implementation
- ANN: A library for approximate NNS
- Splitting rule with a rigorous analysis: It’s okay to be skinny if your friends are fat (Maneewongvatana and Mount, 1999)
Lecture 4: (1/16): Curse of dimensionality [notes] [scribe notes]
- Locality sensitive hashing (LSH) (Wikipedia)
- The paper that led to MinHash at Alta Vista: Identify and filtering near-duplicate documents (Broder, 2000)
- Near-optimal hashing algorithms for approximate nearest neighbor in high dimension (Andoni and Indyk, 2008)
- These notes give a short formal proof of the JL lemma: Dimension reduction notes from CSE 525
- Faster dimension reduction (Ailon and Chazelle, 2010)
- The original JL paper: Extensions of Lipschitz mappings into a Hilbert space (Johnson and Lindenstrauss, 1984)

Week 3: Learning theory

Lecture 5 (1/21): Generalization theory [notes] [scribe notes]
- A theory of the learnable (Valiant, 1984)
- Understanding deep learning requires rethinking generalization (Zhang, et. al., 2017)
  A phenemenon that is currently not fully explained is the the generalizability of models from deep learning. These models are often heavily overparameterized, so they "should" overfit according to the traditional theory. Yet even without explicit regularization, these models generalize unexpectedly well from training data.
Lecture 6 (1/23): Regularization [notes] [scribe notes]
- L1 regularization—also known as “basis pursuit” in this context—is a fundamental building block for compressive sensing.
- A matrix version of L1 regularization ("atomic norm" minimization) is useful for matrix completion and the Netflix problem

Week 4: Principal component analysis

Lecture 7 (1/28): Introduction to PCA [notes] [scribe notes]
- A Different Kind of Gene Mapping: Comparing Genetic and Geographic Structure in Europe
- Eigenfaces blog post
- Everything you didn’t know about PCA
- PCA explained visually - possibly useful visualization tools
Lecture 8 (1/30): Computing the principal components [notes] [scribe notes]
- Power method still powerful
- Block methods of the power method are based on Krylov iteration

Week 5: Low-rank approximation

Lecture 9 (2/4): Singular value decomposition [notes] [scribe notes]
- Singular value decomposition and applications
- Recently, low rank approximations were proposed to speed up large language models: see e.g. LoRA.
Lecture 10 (2/6): Tensors and tensor low-rank decomposition [notes] [scribe notes]
- A blog post describing Spearman’s original experiment
- A blog post about the method of moments in research on evolution
- Tensor Decompositions and Applications by Kolda and Bader

Week 6: Spectral graph theory

Lecture 11 (2/11): Graphs as matrices [notes] [scribe notes]
- Dan Spielman’s lecture notes for a semester-long course on Spectral Graph Theory.
- For some more advanced material, see these courses by Amin Saberi (Stanford) and Shayan Oveis Gharan (UW).
- A general-audience scientific talk James Lee (UW prof) gave on the unreasonable effectiveness of spectral graph theory
- Google’s first ranking algorithm PageRank can be seen as envisioning the web graph as a physical system.
- Anup Rao (UW prof) advocates using spectral methods to analyze trade networks.
- A little tutorial: Spectral clustering for beginners
Lecture 12 (2/13): Spectral clustering [notes] [scribe notes]
- Cheeger's original paper(paywalled though...)
- A full proof of the discrete Cheeger's inequality
- The paper on higher-order Cheeger inequalities by James (UW), Shayan (UW), Luca Trevisan

Week 7: Mathematical programming

Lecture 13 (2/18): Compressive Sensing [notes] [scribe notes]
- A survey talk of Emmanuel Candes on compressive sensing
- A faster single-pixel camera
- Discussion of the applications in medical imaging
- A CSE 525 lecture on analysis of random sensing matrices
- A completely different type of algorithm for compressive sensing via non-convex optimization
Lecture 14 (2/20): Linear programming [notes] [scribe notes]
- The effectiveness of convex programming in the information and physical sciences
- We used to (and hopefully will again in the future?) teach an entire course on convex optimization
- A CSE 525 lecture on semi-definite programming

Week 8: Online learning

Lecture 15 (2/25): The multiplicative weights algorithm [scribe notes]
- Lecture notes for multiplicative weights from Stanford
- MW was rediscovered multiple times. One such instance is the famous AdaBoost paper.
- A nice (albeit a bit advanced) survey on multiplicative weights and its applications
Lecture 16 (2/27): Solving linear programs with multiplicative weights [notes] [scribe notes]
- The full version of the survey above also has a nice exposition of matrix multiplicative weights

Week 9: Sampling

Lecture 17 (3/4): Markov Chain Monte Carlo [notes] [scribe notes]
Lecture 18 (3/6): Langevin Dynamics and Diffusion Models [scribe notes]
- A nice writeup on Langevin dynamics
- The original DDPM paper
- It's impossible to cover stochastic calculus in one lecture. If you want to dedicate a lot of time to understand it properly, a classic reference is a book by Bernt Øksendal

Week 10: (Special topic) Robust statistics

Lecture 19 (3/11): Learning with outliers [scribe notes]
- Lecture notes from a seminar I taught at UW
Lecture 20 (3/14): Spectral signatures and high-dimensional robust statistics [scribe notes]
- Lecture notes from the seminar I taught at UW
- A video that contains a tight proof of the spectral signature lemma, using weighted removal

Problem sets

Homework 1. Due date: Jan 15
Homework 2. Due date: Jan 22
- newsgroup_data.yaml
Homework 3. Due date: Jan 29
- A primer on gradient descent
Homework 4. Due date: Feb 5
- Genomic dataset
- Encoding information
Homework 5. Due date: Feb 12
Homework 6. Due date: Feb 19
- friends.csv
Homework 7. Due date: Feb 26
- how to install cvxpy
- wonderland-tree.png, or if it's easier to use, the 2D binary array as wonderland-tree.txt
- jinx_corrupted.png
- The documentation for tv can be found here
Homework 8. Due date: March 5
- close.csv and tickers.csv
Homework 9. Due date: March 12
- parks.csv

Submitting your assignments

Assignments are released on Tuesdays, and everything (code + written answers) is due at 11:59pm on the following Wednesday. Each assignment is based on the week's lecture and reading material, and can be done alone, or with one other student enrolled in the course. In the latter case, only one student should submit files.

For the "written" part, you will submit your answers via Gradescope. If you are enrolled in the class, then during the first week, you should receive an email about your enrollment. You should typeset your homeworks using LaTeX or some other system that supports both code snippets and mathematical formulas.
For the programming part, you are welcome to use whatever programming language you choose, though you are encouraged to use Python together with the Numpy and Pyplot packages. You will turn in all your code files on Canvas. These should be submitted as a single zip file. If you do not work with a partner, please name the file lastname.zip where "lastname" is replaced by your last name. If you work with a partner (recall that only one person should submit), please use the naming convention: lastname1-lastname2.zip. You are allowed to submit multiple times. New submissions will replace the old submission. Note that all your code files should be submitted in this way; some of your code will also be required in the written part, as specified in the assignment.

Collaboration policy

You are allowed to refer to your course notes, as well any books, lecture notes, papers, and additional resources that are directly linked from the course web page. Remember to cite the source appropriately and always write discussions and homework answers in your own words.

It is also permissible to use general-purpose references for the programming languages and libraries that you employ. Use of ChatGPT or other AI systems is permitted but be warned: the instructors have tried using state-of-the-art systems for these homeworks and their solutions are often wildly incorrect. If you submit something written by an AI that's nonsense do not expect partial credit.

You may discuss assignments at a high level with other groups in the class, as well as with the course staff during office hours, or on Canvas.

Guidelines, Resources and Expectations

The following is consistent with the standards set at the University of Washington at large.

Academic Integrity

The University takes academic integrity very seriously. Behaving with integrity is part of our responsibility to our shared learning community. If you’re uncertain about if something is academic misconduct, ask me. I am willing to discuss questions you might have.

Acts of academic misconduct may include but are not limited to:

Cheating (working collaboratively on quizzes/exams and discussion submissions, sharing answers, and previewing quizzes/exams)
Plagiarism (representing the work of others as your own without giving appropriate credit to the original author(s))

Concerns about these or other behaviors prohibited by the Student Conduct Code will be referred for investigation and adjudication by (include information for specific campus office).

Students found to have engaged in academic misconduct may receive a zero on the assignment (or other possible outcome).

Conduct

The University of Washington Student Conduct Code (WAC 478-121) defines prohibited academic and behavioral conduct and describes how the University holds students accountable as they pursue their academic goals. Allegations of misconduct by students may be referred to the appropriate campus office for investigation and resolution. More information can be found online here.

Accessibility and Disability Resources

Your experience in this class is important to me. It is the policy and practice of the University of Washington to create inclusive and accessible learning environments consistent with federal and state law. If you have already established accommodations with Disability Resources for Students (DRS), please activate your accommodations via myDRS so we can discuss how they will be implemented in this course.

If you have not yet established services through DRS, but have a temporary health condition or permanent disability that requires accommodations (conditions include but not limited to; mental health, attention-related, learning, vision, hearing, physical or health impacts), contact DRS directly to set up an Access Plan. DRS facilitates the interactive process that establishes reasonable accommodations. Contact DRS at disability.uw.edu.

Religious Accomodations

Washington state law requires that UW develop a policy for accommodation of student absences or significant hardship due to reasons of faith or conscience, or for organized religious activities. The UW’s policy, including more information about how to request an accommodation, is available at Religious Accommodations Policy (https://registrar.washington.edu/staffandfaculty/religious-accommodations-policy/). Accommodations must be requested within the first two weeks of this course using the Religious Accommodations Request form (https://registrar.washington.edu/students/religious-accommodations-request/).

Safety

Call SafeCampus at 206-685-7233 anytime – no matter where you work or study – to anonymously discuss safety and well-being concerns for yourself or others. SafeCampus’s team of caring professionals will provide individualized support, while discussing short- and long-term solutions and connecting you with additional resources when requested.

The University of Washington prohibits sex discrimination and sex-based harassment and expects all UW community members to respect one another in our shared academic and work environments. Sex discrimination and sex-based harassment can include sexual assault, relationship violence, stalking, unwanted sexual contact, sexual exploitation, sexual harassment, and discrimination based on sex.

Students who believe they have experienced sex discrimination or sex-based harassment are encouraged to contact a Title IX case manager by making a Title IX report. The case manager can provide guidance on available support resources and resolution options.

^{†. Course schedule and contents subject to change and will be announced throughout the term.↩}