Lecture 1

Logistics & Stable Matching

CSE 421 Autumn 2025

1

Course Logistics

2

Instructor

Andrea Coladangelo (you can call me Andrea)

coladan@cs.washington.edu

​

Research focus: Quantum information

Office: CSE2 212

Office Hours: Mondays 3pm

3

Course staff

• Head TAs: Jay Dharmadhikari, Timothy Tran
• TAs: Toby Thornburg, Diana Hsieh, Darin Ershov, Frank Liu, Ronald Lin, Parker Vladimiroff
• Contact Andrea for questions about logistics, extenuating circumstances, etc.

4

Day 1 checklist

• Find the course website: https://andreacoladangelo.com/teaching/cse421au25,�and read the syllabus.
• Make sure you are on the following course resources: Ed, Gradescope.�Ask a TA for help if necessary.
• Attend your first section tomorrow!
• (Office hours start Monday)
• (Problem set 1 is posted tomorrow)

5

How to succeed in this class

• If possible, attend lecture and sections and ask questions/interact. Attendance is always optional, but correlated strongly with final grade.
• Put effort into solving the HW problems! (This is the #1 most important thing to do)
• Expect a mixture of easier and harder problems on HWs. Some problems will require more thinking than usual. If possible, give yourself enough time to work on the HWs (don’t start at the last minute). You’ll get much more out of the HWs and the class!

6

​

Designing algorithms is almost like an art: you cannot learn this skill by just listening to lectures or reading a textbook. You have to spend time trying.

Coursework

• 8 problem sets due on Thursdays at 11:59 PM
• Typically 1 more mechanical + 2 or 3 long-form problems
• You are encouraged to collaborate with other students but write-ups must be done individually and cannot be shared/distributed
• Use of external resources (including AI) is only allowed to clarify concepts from class or get an alternative perspective. You are not allowed to use AI with the intention of finding the solution to a HW problem. �Make sure to read the syllabus. You can ask Andrea if you have any questions.

7

Late submissions

• You have 6 tokens for 24h late submissions, no questions asked.
• You can use up to 3 on the same HW if you like.
• After the 6 extensions are exhausted:
• Submissions up to 24-hours late are graded with a 50% penalty.
• Submissions after 24-hours are given zeros.
• Extenuating circumstances are of course separate, and should be discussed directly with Andrea.

8

Exams and grading scheme

• Midterm: TBA
• Final: Monday December 8th, 2:30-4:20pm (same room as lecture)
• Grading scheme:
• 8 problem sets: 50%
• Midterm: 22%
• Final: 28%

9

Textbook

• The optional reference textbook is “Algorithm Design” by Kleinberg and Tardos.
• It is not required — all required content can be extracted from the lecture notes and quiz section materials.

10

Goals & structure

• Develop a toolkit for designing efficient algorithms
• Develop techniques for proving correctness and analyzing their properties

11

The two main goals:

High-level course structure:

• Lectures teach various families of algorithms, and show several applications
• Sections and HWs cover examples of instantiations and analysis pertinent to that week. HWs also contain problems where you’ll have to figure out which families of algorithms to use, and how to put them together.
• Exams: ~70% are (slight variations on) problems you have already seen. ~30% problems that are up your alley but require a bit more thought.

Properties of an algorithm

What should we be optimizing for?

• Computational efficiency
• Time, space, communication, etc.
• Historically, important parameters because computers were slow and weak
• Today, important parameters because computations are large
• Fairness
• Does my algorithm have unintended consequences? Very important as we apply algorithms in practice.
• In my research world of quantum computing:
• e.g. how robust is the algorithm to errors/noise?

12

Today

13

• Introduce the stable matching problem
• Gale-Shapley algorithm

Stable Matching

14

The matching problem

• Goal: Given a set of preferences among hospitals and doctors, design an admissions process to allocate doctors to hospitals.
• Many other applications:
• Assign TAs to courses
• High schoolers to magnet schools
• Users to internet servers

15

The matching problem

• Goal: Given a set of preferences among hospitals and medical residents, design a process to allocate residents to hospitals.
• What might we want to optimize for?
• What properties does our optimal solution have?
• Can we always find such an optimal solution?

16

The matching problem, more formally

17

The matching problem, more formally

18

Questions

19

Does a stable matching always exist?

Can we find a stable matching efficiently?

We’ll explore these two questions in the rest of this lecture, and the next.

Turns out the answer is yes.

Turns out the answer is yes.

Key idea: “propose and reject”

• One at the time, unmatched hospitals “propose” to the highest resident on their preference list (that they haven’t already proposed to).
• Residents:
• If free: accept proposal
• If already matched: accept if proposer is preferred to current match, reject otherwise
• Continue until everyone is matched.

Gale-Shapley algorithm (1962)

• One at the time, unmatched hospitals “propose” to the highest resident on their preference list (that they haven’t already proposed to).
• Residents:
• If free: accept proposal
• If already matched: accept if proposer is preferred to current match, reject otherwise
• Continue until everyone is matched.

Gale-Shapley algorithm (1962)

Questions:

1. Does the algorithm terminate (if so, what’s the running time?)

2. Does it find a stable matching?

Gale-Shapley: example walkthrough

Gale-Shapley: analysis

(This is where we prove that the algorithm has the desired properties)

2. Does it find a stable matching?

We’ll start with Question 1. We’ll answer/analyze Question 2 in the next lecture.

Gale-Shapley: proof of termination

At that point, by Claim 1, all other residents are matched. So this last proposal will be accepted, and everyone will be matched.

Gale-Shapley: proof of termination

How does one come up with this proof?

There isn’t a recipe.. but one thing that helps:

• Try to run the algorithm on a few examples, and look for patterns. �More on this in the next lecture, when we’ll prove that the algorithm finds a stable matching.

Gale-Shapley: wrapping up runtime

Gale-Shapley: wrapping up runtime

Measuring efficiency: The RAM model

Note: we will assume we are working in the RAM model:

The history of the propose and reject algorithm

Gale and Shapley 1962

30

Shapley winning the 2012 Economics Nobel Prize (with Roth)