CSE 421: Introduction to Algorithms

Spring, 2019

Shayan Oveis Gharan

MWF 1:30-2:20, CSE2 G01
Office hours in CSE 636
M/W/F 2:30-3:20
Also, T 4:30-5:20

Email list:
Class email list: cse421a_sp19     [archives]

Please send any e-mail questions about the course to cse421-staff@cs.washington.edu.

Plesae use Piazza for course related questions.

Algorithm Design by Jon Kleinberg and Eva Tardos, Addison-Wesley, 2006.

We will cover almost all of chapters 1-8 of the Kleinberg/Tardos text plus some additional material from later chapters. In addition, I recommend reading chapter 5 of Introduction to Algorithms: A Creative Approach, by Udi Manber, Addison-Wesley 1989. This book has a unique point of view on algorithm design.

Another handy reference is Steven Skiena's Stonybrook Algorithm Repository

Grading Scheme (Roughly):

Homework 50%
Midterm 15-20%
Final Exam 30-35%

Lecture Slides
Lecture Topic Slides Notes Reading Assignment
Lecture 1 (04/01/19) Stable Matchings slides notes Section 1.1 of KT
Lecture 2 (04/03/19) Stable Matchings slides notes Section 1.2 of KT
Lecture 3 (04/05/19) Overview, Asymptotics slides notes Chapter 2 of KT
in-class exercise
Lecture 4 (04/08/19) Graphs, Trees slides notes Section 3.1 of KT
in-class exercise
Lecture 5 (04/10/19) BFS, Connected Comps slides notes Section 3.2,3.3 of KT
in-class exercise
Lecture 6 (04/12/19) Bipartiteness slides notes Section 3.4 of KT
BFS Notes
Lecture 7 (04/15/19) DFS, Topological Sorting slides notes Section 3.2, 3.6 of KT
in-class exercise
Lecture 8 (04/17/19) Greedy Alg: Interval Scheduling, slides notes Section 4.1 of KT
Lecture 9 (04/19/19) Interval Partitioing/MST slides notes Section 4.1, 4.5 of KT
Lecture 10 (04/22/19) Minimum Spanning Tree Problem slides notes Section 4.4,4.6 of KT
Lecture 11 (04/24/19) Union Find DS slides notes Section 4.6 of KT
Notes on Union Find, Distinct Edges
Lecture 12 (04/26/19) Dijkstra's Alg slides notes Section 4.4 of KT
Dijkstra's Alg
Lecture 13 (04/29/19) Master Theorem, Closest Point slides notes Section 5.1, 5.2 of KT
Lecture 14 (05/01/19) Integer Multiplication slides notes Section 5.4, 5.5 of KT Integer Multiplication Pf
Lecture 15 (05/03/19) Approx Algorithms slides notes Section 5.4 of KT
Vertex Cover Approx Alg
(05/06/19) Midterm
Lecture 16 (05/08/19) Algorithm Design by Induction slides notes Set Cover
Sections 5.1,5.2,5.4,5.8 of Manber's book
Lecture 17 (05/10/19) Weighted Interval Scheduling slides notes Section 6.1,6.2 of KT
Lecture 18 (05/13/19) Knapsack slides notes
Lecture 19 (05/15/19) RNA Secondary Structure, Sequence Alignment slides notes Section 6.4,6.5 of KT
Lecture 20 (05/17/19) Longest Path in a DAG, LIS, Shortest Paths slides notes Section 6.6 of KT
Lecture 21 (05/20/19) Network Flow slides notes Section 7.1 of KT
Lecture 22 (05/22/19) Max Flow-Min Cut slides notes Section 7.2,7.5 of KT
Lecture 23 (05/24/19) Hall's Condition slides notes
(05/27/19) No Class: Memorial Day
Lecture 24 (05/29/19) Edge Disjoint Paths, Image Segmentation slides notes Section 7.6 of KT
Lecture 25 (05/31/19) Image Segmentation, Projection Proposal slides notes Section 7.9,7.10,7.11 of KT
Lecture 26 (06/03/19) Polynomial-time Reductions slides notes Section 8.1 of KT
Lecture 27 (06/05/19) NP-Completeness slides Section 8.3,8.4 of KT
Lecture 28 (06/07/19) Polytime Maxflow/Linear Programming slides
Final Review (06/09/19) slides notes

Homeworks [Grading guidelines]:

Homework submission is due via Canvas

TA Office hours Room
Aditya Saraf Tue 2:30-3:20 Allen 021
Guanghao Ye Wed 11:30-12:20 Gates 151
Anny Kong Thu 10:00-10:50 Gates 151
Justin Mcgowen Tue 3:30-4:20 Gates 153
Zongyuan Chen Mon 10:30-11:20 Allen 021
Gabriel Cadamuro
Leiyi Zhang
Liangyu Zhao Tue 11:00-11:45 Gates 153
Alice Zhao


  • Midterm exam:
    In CSE2 G01 at the regular class time on Monday, 06-May-2019. This will be open book and open notes, hard copies only. The coverage includes all topics through divide and conquer. An old sample midterm is available along with sample solutions. Please try to solve the problems before looking at the asnwer sheet.
    There will be a review session on Sunday, 05-May-2019 at 3:00 pm in EE 125. Please bring your questions.
  • Final exam:
    In CSE2 G01 on Monday, 10-Jun-2019 at 2:30-4:20 pm as shown in the UW exam schedule. Similar to midterm, it will be open book and open notes, hard copies only.
    There is an practice final from previous offerings of the course. here is the solutions to the sample final. Here is another old final. And here is the solution. There will be a review session on Sunday, 09-Jun-2019 at 3:00 pm. in GWN 201. Please bring your questions.

Portions of the CSE 421 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 421 Web: © 1993-2017, Paul G. Allen School of Computer Science and Engineering, University of Washington.