CSE 421: Introduction to Algorithms

Spring, 2024

Shayan Oveis Gharan

MWF 1:30-2:20PM, in: CSE2 G20
Office hours Allen Center 636
M 12:30-1:20, W 2:30-3:20 and F 12:30-1:20

Email list:
Class email list: cse421a_sp24     [archives]

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

Plesae use ed for course related questions.

Textbook:
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%
Extra Credit Problems Can increase final GPA by 0.1
Quizzes Can Increase final GPA by 0.1

Lecture Scribble Notes
Lecture Slides
Lecture Topic Slides/Notes Inclass Exercise Reading Assignment
Lecture 1 (03/25/24) Stable Matchings pdf Section 1.1 of KT
Lecture 2 (03/27/24) Stable Matchings/Induction pdf Section 1.2 of KT
Section 1 (03/28/24) Stable Matching, Induction pdf, Solution
Lecture 3 (03/29/24) Stable Matching, Asymptotics pdf, annotated
Lecture 4 (04/01/22) Graphs, Induction pdf inclass-exercise
Chapter 2 of KT
Lecture 5 (04/03/24) Trees pdfannotated
Section 3.1 of KT
BFS
Section 2 (04/04/24) BFS pdfpdf
Lecture 6 (04/05/24) Connected Components,Bipartiteness pdf
Section 3.2,3.3,3.4 of KT
BFS + Conn Comp Code
Lecture 7 (04/08/24) DFS, Topological sorting pdf
Section 3.2
Lecture 8 (04/10/24) Topological Sorting, Interval scheduling pdf Section 3.6, 4.1 of KT
Section 3 (04/11/24) DFS,Directed Graphs,Induction pdf, solution Section 3.6 of KT
Lecture 9 (04/12/24) Interval Schedule/Partitioning pdf Section 4.1,4.5 of KT
Lecture 10 (04/15/24) Greedy: Minimum Spanning Tree pdf Section 4.4 of KT
Lecture 11 (04/17/24) Union-Find Data Structure pdf Section 4.4 of KT
Supplement notes for Union Find/Kruskal's alg
Section 4 (04/18/24) Greedy/Kruskal pdf, solutions
Lecture 12 (04/19/24) Divid and Conq pdf
Sections 4.6, 5.1 of KT
Lecture 13 (04/22/24) Divide and Conq: Closest Pair pdf Sections 5.1,5.2 of KT
Lecture 14 (04/24/24) Integer Multiplication, Midpoint pdf Sections 5.4,5.5 of KT
Section 5 (04/25/24) Midterm Review slides
Lecture 15 (04/26/24) Approx Algorithms pdf Section 4.4 of KT
(04/29/24) Midterm (10:30-11:20)
Lecture 16 (05/01/24) Approximation Algorithms, Dynamic Programming pdf
Section 6 (05/02/24) Approximation Algorithms/DP pdf, solution
Lecture 17 (05/03/24) DP: Interval Scheduling pdf Section 6.1 of KT
Sections 5.1,5.2,5.4,5.8 of Manber's book
Lecture 18 (05/06/24) RNA Secondary structure pdf Sample Proof of Interval Scheduling
Section 6.2 of KT
Lecture 19 (05/08/24) Longest path in DAG, LIS, Shortest Path pdf Section 6.2, 6.4 of KT
Section 7 (05/09/24) DP pdf, solutions
Lecture 20 (05/10/24) Shortest Path, Network Flow pdf Section 6.5, 6.6 of KT
Lecture 21 (05/13/24) Network Flow pdf Section 7.1 of KT
Lecture 22 (05/15/24) Max Flow-Min Cut pdf Section 7.2 of KT
Section 8 (05/16/24) Network Flow pdf, solution
Lecture 23 (05/18/24) Maximum matching, Hall's Condition pdf Section 7.2 of KT
Lecture 24 (05/20/24) Edge Disjoint Paths, Image Segmentation pdf Section 7.6 of KT
Lecture 25 (05/22/24) Linear Programs Intro pdf supplement-note-vertex-cover
Section 9 (05/23/24) LP pdf, solutions
Lecture 26 (05/24/24) LP Duality pdf
(05/27/24) No Class: Memorial Day
Lecture 27 (05/29/24) Polynomial Time Reductions pdf Section 7.9, 8.1 of KT
Section 10 (05/30/24) Reductions/Final Review
Lecture 28 (05/31/24) NP-Completeness pdf Section 7.10,7.11,8.3 of KT
(06/03/24) Final Exam (2:30-4:20 CSEII G20)

Homeworks [Grading guidelines]:

Homework submission is due via Gradescope

TA Office hours Location
Xiyang Liu Fri 9:00-10:00 AM Gates 150
Marian Dietz Fri 11:30-12:20 PM Gates 150
Raymond Patrick Guo Fri 2:30-3:30 Gates 150
Robert Stevens Tue 11:30-12:20 Gates 150
Airei Fukuzawa Tue 12:30-1:20 PM Gates (CSE II) 150
Aman Thukral Tue 2:30-3:30 Gates (CSE II) 121
Tom Tian Tue 3:30-4:30 Gates (CSE II) 152
Dorna Abdolazimi Fri 3:30-4:20 Gates 150
Sophie Lin Robertson Wed 10:30-11:30 Gates 150
Sela Navot Wed 11:30-12:30 Gates 131
Albert Weng Wed 3:30-4:30 Gates 150

Exams:

  • Midterm exam:
    At 1:30-2:20 Gates G20 Monday 29-April-2024 This will be open book and open notes, hard copies only. You are not allowed to access internet. The coverage includes all topics through divide and conquer. An old midterm with sample solutions. Here is the Midterm exam of Spring 2021. Please try to solve the problems. I will upload the solutions by Friday. We will review solutions in sections this Thursday April 25th.
  • Final exam:
    At 2:30-4:20 Gates G20 Monday 3-Jun-2024. Similar to midterm, it will be open book and open notes, hard copies only.
    There is a practice final from previous offerings of the course. --here is the solutions to the sample final. Here is another old final. Here is Final of 2018. No solution will be given for this one. Please practice this final in a timed interval Final Review Slides

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.