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

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

Plesae use ed for course related questions.

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 | 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

- Homework 1 due Thursday, 8-April at 11:59PM.
- Homework 2 due Thursday, 15-April at 11:59PM.
- Homework 3 due Thursday, 22-April at 11:59PM.

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.