Lecture 1

Logistics & Stable Matching

CSE 421 Autumn 2026

1

Course Logistics

2

Instructor

Andrea Coladangelo (you can call me Andrea)

coladan@cs.washington.edu

​

Research focus: Quantum information

Office: Gates 212

Office Hours: Wednesday 4.30pm, Gates 371

3

TAs

• Brice Liu, Sophia Li, Michael Whitmeyer, Runjia Li, Aaryan Pawar, Toprak Yildirim, Parker Vladimiroff, Sami Badal Khan, Vinay Pritamani, Escher Crawford.
• Contact Andrea for questions about logistics, extenuating circumstances, etc.

4

Day 1 checklist

• Find the course website: https://andreacoladangelo.com/teaching/cse421au26,�and read the syllabus.
• Make sure you are on the following course resources: Ed, Gradescope.�Ask me for help if necessary.
• Attend your first section tomorrow!
• (Office hours start Monday)
• (HW 1 is posted later today - due Thursday next week)

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 AI (and other external resources) is only allowed to understand or clarify concepts from class, or go beyond the class material. You are not allowed to use AI with the intention of finding the solution to a HW problem. �Make sure to read the policy (in 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 14th, 2:30-4:20pm (same room as lecture, and possibly a second one)
• Grading scheme:
• 8 problem sets: 36%
• Midterm: 28%
• Final: 36%

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 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 and analysis related 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: ~50% are (slight variations on) problems you have already seen. ~50% 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 medical residents, design a process to allocate residents 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

We will simplify and consider: hospitals, residents

The matching problem, more formally

• Input: The preference lists of residents and hospitals (each agent ranks every agent in the other set)
• Goal: Output a stable matching.

17

A matching is an assignment of each resident to one hospital (and viceversa).

What does it mean for a matching to be stable?

We say that an unmatched pair is unstable if both and prefer each other to their current match.

​

The matching problem, more formally

• Input: The preference lists of residents and hospitals (each agent ranks every agent in the other set)
• Goal: Output a stable matching.

18

A matching is an assignment of each resident to one hospital (and viceversa).

What does it mean for a matching to be stable?

We say that an unmatched pair is unstable if both and prefer each other to their current match.

We say that a matching is stable if it contains no unstable pair.

Why stability? It’s a desirable condition: no side-deals are incentivized.

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)

Initially all in and in are free

while there is a free

  Let be highest on s list that has not proposed to yet

  if is free

         match

  else // is not free

         Let be the current match of .

      if prefers to

  unmatch

  match

Questions:

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

2. Does it find a stable matching?

Let and be the sets of hospitals and residents respectively.

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

Claim 1: if some has proposed to the last resident on their list,�then all residents are matched.

Proof: Notice that once a resident is matched, they remain matched forever.

Claim 2: The algorithm terminates after proposals.

Proof: Since we never repeat a proposal, and each hospital has a list of length , it takes at most proposals until the first hospital has proposed to the last resident on its list.

Since proposes to residents in order of preference, when proposes to the last resident on its list, it must have proposed to every other resident already. So, every other resident is already matched (and the last resident is free).

Gale-Shapley: proof of termination

Claim 1: if some has proposed to the last resident on their list,�then all residents are matched.

Proof: Notice that once a resident is matched, they remain matched forever.

Claim 2: The algorithm terminates after proposals.

Proof: Since we never repeat a proposal, and each hospital has a list of length , it takes at most proposals until the first hospital has proposed to the last resident on its list.

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

Since proposes to residents in order of preference, when proposes to the last resident on its list, it must have proposed to every other resident already. So, every other resident is already matched (and the last resident is free).

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

We have shown that the algorithm takes at most proposals to terminate.

But how long does each proposal take to run?

For each proposal, we might need to do a comparison: check whether a resident prefers or . How long does a comparison take?

If we do things naively, we have to go through the resident’s preference list until we encounter or . This could take time , which would result in an overall runtime for the entire algorithm.

Is there a better way?

Yes, the idea is to start by pre-computing a table of “inverses”.

Gale-Shapley: wrapping up runtime

Key idea to implement comparisons efficiently: start by pre-computing a table of “inverses”.

Inv[i][j] answers the question: “resident , what rank is hospital in your list?”

Crucially, we compute this table once at the beginning, and after this each comparison only takes time .

How long does it take to compute the table of inverses?

This only takes time (you should convince yourself of this)

So, overall running time = (pre-computation time) + (#proposals)(comparison time)

=

Measuring efficiency: The word-RAM model

• Memory is divide into “words” of bits. For inputs of size , assume �(i.e. one word can store a number up to ).
• Each simple operation on words (arithmetic, evaluating if loop criteria, call, increment counter, inserting a word in an array) takes one time step.
• Accessing any one word in memory takes one time step (this is what the fancy acronym RAM = “Random Access Machine” refers to).
• Measuring algorithm efficiency
• Let input be with each representing one word.
• Runtime of algorithm is the number of “simple operations” taken by the algorithm in RAM model.

For this course, we will assume we are working in the word-RAM model (unless specified otherwise):

The history of the propose and reject algorithm

Gale and Shapley 1962

• The original paper was about matching men and women in marriage.
• Gale and Shapley’s algorithm defined the proposers as the men and the receivers as the women.
• We will see next week that the GS algorithm is proposer-optimal but not receiver-optimal.
• As originally stated, the GS algorithm favored being a man. This social implication was not recognized for some time!
• Is fairness possible? In some cases, yes. But this is an area of research!

31

Shapley winning the 2012 Economics Nobel Prize (with Roth)