CSE 421: Introduction to Algorithms

Spring, 2022

Shayan Oveis Gharan

MWF 10:30-11:20, in: KNE 220
Office hours Allen Center 636
M/W 11:30-12:20
Also, Tue 12:30-1:20 95223400112

Email list:
Class email list: cse421a_sp22     [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/28/22) Stable Matchings pdf Section 1.1 of KT
Lecture 2 (03/30/22) Stable Matchings pdf Section 1.2 of KT
Lecture 3 (04/01/22) Induction, Asymptotics pdf
Lecture 4 (04/04/22) Asymptotics, Graphs pdf In Class Exercise
Chapter 2 of KT
PSS 1 (04/05/22) Stable Matching, Induction pdf
Lecture 5 (04/06/22) Trees pdf
Section 3.1 of KT
Induction on Graphs
Lecture 6 (04/08/22) BFS pdf
Section 3.2 of KT
Lecture 7 (04/11/22) Connected Comps, Bipartiteness pdf In Class Exercise
Section 3.3,3.4 of KT
BFS + Conn Comp Code
PSS 2 (04/12/22) Trees, BFS pdf
Lecture 8 (04/13/22) DFS, Topological Sorting pdf Section 3.2 of KT
Lecture 9 (04/15/22) Topological Sorting/ Interval Scheduling pdf In Class Exercise Section 3.6 of KT
Lecture 10 (04/18/22) Greedy: Interval Scheduling/Partitioning pdf Section 4.1,4.5 of KT
PSS 3 (04/19/22) Trees, BFS pdf
Lecture 11 (04/20/22) Minimum Spanning Tree pdf Section 4.4 of KT
Lecture 12 (04/22/22) Union Find DS, Divid and Conq pdf
Sections 4.6, 5.1 of KT
Union Find Pseudocode
Lecture 13 (04/25/22) Divide and Conq: Closest Pair pdf Sections 5.1,5.2 of KT
PSS 4 (04/26/22) Greedy/Kruskal pdf
Lecture 14 (04/27/22) Divide and Conq: Integer Multiplication pdf Sections 5.4,5.5 of KT
Lecture 15 (04/29/22) Divide and Conq: Midpoint, Approx Algorithms pdf Section 4.4 of KT
(05/02/22) Midterm (10:30-11:20)
Lecture 16 (05/04/22) Approximation Algorithms, Dynamic Programming pdf
Lecture 17 (05/06/22) 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/09/22) DP: Knapsack pdf Sample Proof of Interval Scheduling
Section 6.2 of KT
PSS 5 (05/10/22) Approx/DP pdf
Lecture 19 (05/11/22) RNA Secondary Structure, Seq Alignment pdf Section 6.2, 6.4 of KT
Lecture 20 (05/13/22) DP: Longest Path in DAG, LIS, Shortest Path pdf Section 6.5, 6.6 of KT
Lecture 21 (05/16/22) Network Flow pdf Section 7.1 of KT
PSS 6 (05/17/22) DP pdf
Lecture 22 (05/18/22) Max Flow-Min Cut pdf Section 7.2 of KT
Lecture 23 (05/20/22) Maximum matching, Hall's Condition pdf Section 7.2 of KT
Lecture 24 (05/23/22) Edge Disjoint Paths, Image Segmentation pdf Section 7.6 of KT
PSS 7 (05/24/22) Network flow pdf
Lecture 25 (05/25/22) Linear Programs Intro pdf
Lecture 26 (05/27/22) LP Duality pdf
(05/30/22) No Class: Memorial Day
Lecture 27 (06/01/22) Polynomial Time Reductions pdf Section 7.9, 8.1 of KT
Lecture 28 (06/03/22) NP-Completeness pdf Section 7.10,7.11,8.3 of KT
(06/06/22) Final Exam (8:30-10:20 KNE 220)

Homeworks [Grading guidelines]:

Homework submission is due via Gradescope

TA Office hours Meeting Id
Allen Thomas Aby Mon 1:30-2:20 PM 96987565486
Robin Yang Tue 10:30-11:20 AM 92155508561
Andreea Ghizila Tue 1:30-2:20 PM Gates 121
William Viet Nguyen Tue 2:30-3:20 PM Gates 150
Motoya Ohnishi Tue 4:30-5:20 PM mohnishi
Ashwin Kishin Banwari Wed 3:30-4:20 PM Gates 121
Jason Waataja Wed 5:00-5:50 4237094217
Ivy Wang Thu 9:30-10:20 AM 2597803488
Mrigank Arora Thu 12:00-12:50 PM Allen 220

Exams:

  • Midterm exam:
    At 10:30-11:20 KNE 220 Monday 02-May-2022 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 and another newer midterm. Here is the Midterm exam of Spring 2021. Please try to solve the problems. I will upload the solutions by Friday. There will be a review session on Saturday, 30-Apr-2022 at 10:00 am, Zoom Meeting ID: 95725223642. Please bring your questions. Slides for the review session.
  • Final exam:
    At 8:30-10:20 KNE 220 Monday 6-Jun-2022. 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. And here is the solution. Here is Final of 2018. No solution will be given for this one. Please practice this final in a timed interval There will be a review session on Saturday, 04-Jun-2021 at 10:00 am. in Zoom Meeting ID: 92420199239. Please bring your questions. 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.