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
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 Slides
| Lecture | Topic | Slides/Notes | Inclass Exercise | Reading Assignment |
|---|---|---|---|---|
| Lecture 1 (03/25/24) | Stable Matchings | Section 1.1 of KT | ||
| Lecture 2 (03/27/24) | Stable Matchings/Induction | 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 | 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 | Section 3.2,3.3,3.4 of KT BFS + Conn Comp Code | ||
| Lecture 7 (04/08/24) | DFS, Topological sorting | Section 3.2 | ||
| Lecture 8 (04/10/24) | Topological Sorting, Interval scheduling | 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 | Section 4.1,4.5 of KT | ||
| Lecture 10 (04/15/24) | Greedy: Minimum Spanning Tree | Section 4.4 of KT | ||
| Lecture 11 (04/17/24) | Union-Find Data Structure | 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 | Sections 4.6, 5.1 of KT | ||
| Lecture 13 (04/22/24) | Divide and Conq: Closest Pair | Sections 5.1,5.2 of KT | ||
| Lecture 14 (04/24/24) | Integer Multiplication, Midpoint | Sections 5.4,5.5 of KT | ||
| Section 5 (04/25/24) | Midterm Review | slides | ||
| Lecture 15 (04/26/24) | Approx Algorithms | Section 4.4 of KT | ||
| (04/29/24) Midterm (10:30-11:20) | ||||
| Lecture 16 (05/01/24) | Approximation Algorithms, Dynamic Programming | |||
| Section 6 (05/02/24) | Approximation Algorithms/DP | |||
| Lecture 17 (05/03/24) | DP: Interval Scheduling | Section 6.1 of KT Sections 5.1,5.2,5.4,5.8 of Manber's book | ||
| Lecture 18 (05/06/24) | DP: Knapsack | Sample Proof of Interval Scheduling Section 6.2 of KT | ||
| Lecture 19 (05/08/24) | RNA Secondary Structure, Seq Alignment | Section 6.2, 6.4 of KT | ||
| Section 7 (05/09/24) | DP | |||
| Lecture 20 (05/10/24) | DP: Longest Path in DAG, LIS, Shortest Path | Section 6.5, 6.6 of KT | ||
| Lecture 21 (05/13/24) | Network Flow | Section 7.1 of KT | ||
| Lecture 22 (05/15/24) | Max Flow-Min Cut | Section 7.2 of KT | ||
| Section 8 (05/16/24) | Network Flow | |||
| Lecture 23 (05/18/24) | Maximum matching, Hall's Condition | Section 7.2 of KT | ||
| Lecture 24 (05/20/24) | Edge Disjoint Paths, Image Segmentation | Section 7.6 of KT | ||
| Lecture 25 (05/22/24) | Linear Programs Intro | |||
| Section 9 (05/23/24) | LP | |||
| Lecture 26 (05/24/24) | LP Duality | |||
| (05/27/24) No Class: Memorial Day | ||||
| Lecture 27 (05/29/24) | Polynomial Time Reductions | Section 7.9, 8.1 of KT | ||
| Section 10 (05/30/24) | Reductions/Final Review | |||
| Lecture 28 (05/31/24) | NP-Completeness | 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
- Homework 1 due Wednesday, 3-April at 11:59PM.
- Homework 2 due Wednesday, 10-April at 11:59PM.
- Homework 3 due Wednesday, 17-April at 11:59PM.
- Homework 4 due Wednesday, 24-April at 11:59PM.
| TA | Office hours | Location |
| Xiyang Liu | Mon 10:30-11:20 AM | Gates 150 |
| Marian Dietz | Mon 3:30-4:20 PM | Gates 121 |
| Raymond Patrick Guo | Mon 4:30-5:30 | Gates 121 |
| 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 | Tue 4:30-5:30 | Gates 151 |
| 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.
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.