CSE 421: Introduction to Algorithms

Spring, 2021

Shayan Oveis Gharan

MWF 1:30-2:20, Zoom Meeting ID: 97771906541
Office hours Zoom Meeting ID: 94137597308
M/W 2:30-3:20
Also, T 4:30-5:20

Email list:
Class email list: cse421a_sp21     [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 Reading Assignment
Lecture 1 (03/29/21) Stable Matchings pdf, Notes Section 1.1 of KT
Lecture 2 (03/31/21) Stable Matchings pdf, Notes Section 1.2 of KT
Lecture 3 (04/02/21) Stable Matchings/Induction pdf, Notes
Lecture 4 (04/05/21) Asymptotics pdfNotes in-class exercise
Chapter 2 of KT
Lecture 5 (04/07/21) Graphs, Trees pdf, Notes
Section 3.1 of KT
Lecture 6 (04/09/21) BFS pdf, Notes
Section 3.2 of KT
Induction on Graphs
Lecture 7 (04/12/21) Connected Comps pdf, Notes Inclass Exercise
Section 3.3,3.4 of KT,
sample alg+proof
Lecture 8 (04/14/21) Bipartiteness pdf,Notes Inclass Exercise Section 3.2 of KT
Lecture 9 (04/16/21) DFS, Topological Sorting pdf,Notes Section 3.6 of KT
Lecture 10 (04/19/21) Greedy: Interval Scheduling/Partitioning pdf, Notes Section 4.1,4.5 of KT
Lecture 11 (04/21/21) Minimum Spanning Tree Section 4.4 of KT
Lecture 12 (04/23/21) Union Find DS, Dijkstra's Alg
Section 4.6 of KT
Lecture 13 (04/26/21) Dijkstra's Alg Section 4.4 of KT
Lecture 14 (04/28/21) Divide and Conq: Closest Pair Section 5.1,5.2 of KT
Lecture 15 (04/30/21) Divide and Conq: Integer Multiplication Section 5.4,5.5 of KT
(05/03/21) Midterm (1:30-2:35 and 10:00-11:05 PST)
Lecture 16 (05/05/21) Approximation Algorithms
Lecture 17 (05/07/21) Algorithm Design By Induction Sections 5.1,5.2,5.4,5.8 of Manber's book
Lecture 18 (05/10/21) DP: Interval Scheduling Section 6.1 of KT
Lecture 19 (05/12/21) DP: Knapsack, Section 6.2, 6.4 of KT
Lecture 20 (05/14/21) RNA Secondary Structure, Seq Alignment Section 6.5 of KT
Lecture 21 (05/17/21) DP: Longest Path in DAG, LIS, Shortest Path Section 6.6 of KT
Lecture 22 (05/19/21) Network Flow Section 7.1 of KT
Lecture 23 (05/21/21) Max Flow-Min Cut, Maximum matching Section 7.2 of KT
Lecture 24 (05/24/21) Matchings Section 7.6 of KT
Lecture 25 (05/26/21) Hall's Conidtion, Edge Disjoint Pathsl Section 7.6 of KT
Lecture 26 (05/28/21) Image Segmentation, Polynomial Time Reductions Section 7.9, 8.1 of KT
(05/31/21) No Class: Memorial Day
Lecture 27 (06/02/21) Polynomial-time Reductions Section 7.10,7.11,8.3 of KT
Lecture 28 (06/04/21) NP-completeness
(06/07/21) Final Exam (2:30-4:20 and 10:00-11:50 PST)

Homeworks [Grading guidelines]:

Homework submission is due via Gradescope

TA Office hours Meeting Id
Savanna J Yee Mon 10:00 AM-10:50 AM 97332958862
Mickey Moonkaen Mon 4:00 PM-4:50 PM 94908850680
Todor Dimitrov Tue 9:00 AM-9:50 AM 7606986951
Albert Liang Zhong Tues 12:30 PM-1:20 PM 95015984293
Aidan Arieh Gottlieb Tue 2:30 PM-3:20 PM 2075377702
Yunkyu Song Tue 5:30 PM-6:20 PM 91882309072
Chase Lee Wed 8:00 AM-8:50 AM 97185046505
Liangyu Zhao Wed 4:00 PM-4:50 PM 3215688552
Mrigank Arora Thu 9:00 AM-9:50 AM 98031098493
Johnson Kuang Thu 11:00 AM-11:50 AM 7935407872

Exams:

  • Midterm exam:
    At 1:30-2:35 (PM) and 10:00-11:05 (PM) Monday 03-May-2021 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.
  • Final exam:
    At 2:30-4:35 (PM) and 10:00-12:05 (PM) on Monday, 7-Jun-2021. 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.