Introduction to Algorithms
CSE 421 · Spring 2025 · University of Washington
Design efficient algorithms, prove them correct, and understand the limits of computation.
Mon, Wed, Fri · 3:30–4:20 pm · Gates 20
Instructor: Chinmay Nirkhe
Course schedule and topics†
March
Thinking like a computer scientist
Topics and reading
- Preamble: course logistics, information, etc.
- The stable matching algorithm
- Pset 1 released due Apr 9th
Literature
- K&T: 1
April
The stable matching algorithm
Topics and reading
- Continuation of stable matching algorithm
- The RAM model for computation
Literature
- K&T: 1.2-2.4
Overview and stable matchings
Graph traversal
Topics and reading
- Overview of the course
- Introduction to greedy algorithms
Literature
- K&T: 3-3.2, 4.1
Graph traversal
Topics and reading
- Breadth- and depth-first search
- Pset 2 released due Apr 16th
Literature
- K&T: 3.3-3.6, DPV: 4.2-4.3
Topological sort and greedy algorithms
Topics and reading
- Topological sort
- Principles of greedy algorithms
- Exchange principle, greedy algorithm proof techniques
- Minimum lateness problem
Literature
- K&T: 4-4.2, DPV: 5-5.1
Graph Traversal and Algorithm Proofs
Greedy approximation and graph algorithms
Topics and reading
- Max cut problem and greedy approximation algorithm
- Shortest path problem, Dijkstra's
Literature
- K&T: 12.4,4.4-4.7, DPV: 4.4-4.7
Minimum spanning trees
Topics and reading
- Minimum spanning trees
- Prim's and Kruskal's algorithms
- k-clustering of datapoints
- Pset 3 released due Apr 23rd
Literature
- K&T: 12.4,4.4-4.7, DPV: 4.4-4.7
Divide and conquer algorithms
Topics and reading
- Binary search and mergesort
- 2D Euclidean shortest distance
- The master theorem
Literature
- K&T: 5-5.4, DPV: 2.2-2.4
Greedy algorithms
Multiplication
Topics and reading
- Matrix, integer, and polynomial multiplication
- Strassen's algorithm
- Karatsuba's algorithm
- Fast Fourier Transform
- Convolution, Image processing
Literature
- K&T: 5.5-5.6, DPV: 2.5-2.6
Randomized divide and conquer
Topics and reading
- Median, Selection, and Quicksort
- Derandomization
- Pset 4 released due Apr 30th
- Pset 4 ¾ released due May 7nd
Literature
- K&T: 13.5, DPV: 2.4
Dynamic programming I
Topics and reading
- Principles of dynamic programming
- Tribonacci numbers
- Edit distance
Literature
- K&T: 6,6.2,6.6, DPV 6.3
Divide and Conquer
Dynamic programming II: The Knapsack problem
Topics and reading
- Brute force algorithm
- Dynamic programming algorithm
- Approximation algorithm
Literature
- K&T: 6.4, 11.8, DPV 6.4
Dynamic programming III
Topics and reading
- Space complexity
- RNA secondary sequences
- Top-down vs bottom-up
Literature
- K&T: 6.1-6.3, 6.5, 6.8, DPV 6.6
Dynamic programming IV
Topics and reading
- Bellman-Ford algorithm
- Applications
Literature
- K&T: 6.8-9, DPV 6.6
May
Midterm review
Question & Answer
Topics and reading
- With Professor Nirkhe. Location: CSE2 G01. Time: 5:30pm-7:30pm.
- No planned topic. Bring any questions you have or topics you want clarified.
- Recording quality may be wanting as it will be on whiteboard.
Negative cycles and network flow
Topics and reading
- Detecting negative cycles with Bellman-Ford
- Definition of max flow and min cut
- Value of a flow, equivalent definitions
- Greedy flow algorithm: Ford-Fulkerson
Literature
- K&T: 7-7.2
Midterm
Exam details
- Location: Lecture Hall CSE2 G20
- Time: 1 Hour. Starts exactly at 3:30 and ends exactly at 4:30.
- Disability Requests that are approved will be in CSE2 345 starting at 3:30 as well.
- Contact head TAs to arrange your specific requirements. Otherwise we assume you are taking standard exam despite your disability requests.
- You may bring 1 8.5x11 page of notes (both sides); see the midterm coversheet for details.
Max flow/min cut
Topics and reading
- Max flow/min cut duality
- Augmenting paths algorithm
- Ford-Fulkerson algorithm
- Application to bipartite matching
Literature
- K&T: 7.2-7.5
Dynamic programming and midterm postmortum
Network flow in polynomial time
Topics and reading
- Finding better augmenting paths
- The Edmonds-Karp algorithm
- Hall's theorem
- Edge disjoint paths
Literature
- K&T: 7.5-7.7,7.12
Flow algorithm applications
Topics and reading
- Network connectivity
- Capacity demands
- Baseball winner problem
Literature
- K&T: 7.5-7.7,7.12
Linear programming I
Topics and reading
- Linear algebra/geometry review
- Optimization problems
- Definition ofa linear program
- Max flow as a linear flow
Literature
- DPV 7-7.3
Network Flow/Linear Programming
Linear programming II
Topics and reading
- Linear programming example
- Max flow as a linear program
- Linear programming duality
Literature
- DPV 7.4-7.5
Linear programming III
Topics and reading
- Linear programming duality
- Max flow/min cut
Literature
- DPV 7.6
Linear programming IV
Topics and reading
- Simplex method
- Interior point and ellipsoid methods
- Boolean functions as LPs
Literature
- DPV 7
Linear Programming/Final Prep
P vs NP and problems that are just too hard
Topics and reading
- Definitions of P, NP, EXP
- Definition of a reduction
- Examples of problems in NP
Literature
- K&T 8.1-8.4, DPV 8.1-8.3
Non-deterministic polynomial time II
Topics and reading
- NP-completeness and the first NP-complete problem
Literature
- K&T 8.1-8.4, DPV 8.1-8.3
NP-Completeness
Non-deterministic polynomial time III
Topics and reading
- 3-SAT is NP-complete
- Vertex Cover is NP-complete
Literature
- K&T 8.1-8.4, DPV 8.1-8.3
June
Non-deterministic polynomial time IV
Topics and reading
- 3-Color is NP-complete
- Traveling Salesman and Hamiltonian Cycle are NP-complete
- Optimization vs Decision
Literature
- K&T 8, DPV 8
Non-deterministic polynomial time V
Topics and reading
- The complexity landscape
- Approximation algorithms for NP-completeness
Literature
- K&T 11,12
Final Review
Question & Answer
Topics and reading
- No planned topic. Bring any questions you have or topics you want clarified.
- Recording quality may be wanting as it will be on whiteboard.
Final
Exam details
- Location: Lecture Hall CSE2 G20
- Time: 2 Hour. Starts exactly at 2:30 and ends exactly at 4:30.
- Disability Requests that are approved will be in CSE2 Rm 371 starting at 2:30 as well.
- Contact head TAs to arrange your specific requirements. Otherwise we assume you are taking standard exam despite your disability requests.
- You may bring 1 8.5x11 page of notes (both sides); see the final coversheet for details.
†. Course schedule and contents subject to change and will be announced throughout the term.↩