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

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 | Inclass Exercise | Reading Assignment |
---|---|---|---|---|

Lecture 1 (03/28/22) | Stable Matchings | Section 1.1 of KT | ||

Lecture 2 (03/30/22) | Stable Matchings | Section 1.2 of KT | ||

Lecture 3 (04/01/22) | Induction, Asymptotics | |||

Lecture 4 (04/04/22) | Asymptotics, Graphs | In Class Exercise | Chapter 2 of KT | |

PSS 1 (04/05/22) | Stable Matching, Induction | |||

Lecture 5 (04/06/22) | Trees | Section 3.1 of KT Induction on Graphs | ||

Lecture 6 (04/08/22) | BFS | Section 3.2 of KT | ||

Lecture 7 (04/11/22) | Connected Comps, Bipartiteness | In Class Exercise | Section 3.3,3.4 of KT BFS + Conn Comp Code | |

PSS 2 (04/12/22) | Trees, BFS | |||

Lecture 8 (04/13/22) | DFS, Topological Sorting | Section 3.2 of KT | ||

Lecture 9 (04/15/22) | Topological Sorting/ Interval Scheduling | In Class Exercise | Section 3.6 of KT | |

Lecture 10 (04/18/22) | Greedy: Interval Scheduling/Partitioning | Section 4.1,4.5 of KT | ||

PSS 3 (04/19/22) | Trees, BFS | |||

Lecture 11 (04/20/22) | Minimum Spanning Tree | Section 4.4 of KT | ||

Lecture 12 (04/22/22) | Union Find DS, Divid and Conq | Sections 4.6, 5.1 of KT Union Find Pseudocode | ||

Lecture 13 (04/25/22) | Divide and Conq: Closest Pair | Sections 5.1,5.2 of KT | ||

PSS 4 (04/26/22) | Greedy/Kruskal | |||

Lecture 14 (04/27/22) | Divide and Conq: Integer Multiplication | Sections 5.4,5.5 of KT | ||

Lecture 15 (04/29/22) | Divide and Conq: Midpoint, Approx Algorithms | Section 4.4 of KT | ||

(05/02/22) Midterm (10:30-11:20) | ||||

Lecture 16 (05/04/22) | Approximation Algorithms, Dynamic Programming | |||

Lecture 17 (05/06/22) | DP: Interval Scheduling | 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 | Sample Proof of Interval Scheduling Section 6.2 of KT | ||

PSS 5 (05/10/22) | Approx/DP | |||

Lecture 19 (05/11/22) | RNA Secondary Structure, Seq Alignment | Section 6.2, 6.4 of KT | ||

Lecture 20 (05/13/22) | DP: Longest Path in DAG, LIS, Shortest Path | Section 6.5, 6.6 of KT | ||

Lecture 21 (05/16/22) | Network Flow | Section 7.1 of KT | ||

PSS 6 (05/17/22) | DP | |||

Lecture 22 (05/18/22) | Max Flow-Min Cut | Section 7.2 of KT | ||

Lecture 23 (05/20/22) | Maximum matching, Hall's Condition | Section 7.2 of KT | ||

Lecture 24 (05/23/22) | Edge Disjoint Paths, Image Segmentation | Section 7.6 of KT | ||

PSS 7 (05/24/22) | Network flow | |||

Lecture 25 (05/25/22) | Linear Programs Intro | |||

Lecture 26 (05/27/22) | LP Duality | |||

(05/30/22) No Class: Memorial Day | ||||

Lecture 27 (06/01/22) | Polynomial Time Reductions | Section 7.9, 8.1 of KT | ||

Lecture 28 (06/03/22) | NP-Completeness | 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

- Homework 1 due Thursday, 7-April at 11:59PM.
- Homework 2 due Thursday, 14-April at 11:59PM.
- Homework 3 due Thursday, 21-April at 11:59PM.
- Homework 4 due Thursday, 28-April at 11:59PM.
- Homework 5 due Thursday, 12-May at 11:59PM.
- Homework 6 due Thursday, 19-May at 11:59PM.
- Homework 7 due Thursday, 26-May at 11:59PM.
- Homework 8 due
**Friday**, 03-Jun at 11:59PM.

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.