Course Calendar
Note that there will not be a class on November 22, the Wednesday before Thanksgiving.

Lecture Slides

• Stable Matching

• Overview

• Graph Traversal

• Greedy Algorithms

• Divide and Conquer

• Dynamic Programming

• Network Flow

• NP-completeness

• Dealing with NP-completeness

• Backtracking for SAT solving

Reading Assignments

• Chapters 1 and 2 of Kleinberg and Tardos
• Chapter 3 of Kleinberg and Tardos
• Sections 4.1-4.7 of Kleinberg and Tardos
• Chapter 5 of Kleinberg and Tardos
• Algebraic Divide and Conquer from Manber's text.
• Section 13.5 of Kleinberg and Tardos
• Chapter 6 of Kleinberg and Tardos
• Sections 7.1-7.3,7.5,7.6,7.11 of Kleinberg and Tardos
• Chapter 8 of Kleinberg and Tardos

Homeworks [Grading and academic integrity guidelines]:

Homework submission is due via Canvas

• Homework 1 due Friday, 6-Oct at 4:00PM.
• Homework 2 due Friday, 13-Oct at 4:00PM.
• Homework 3 due Friday, 20-Oct at 4:00PM.
• Homework 4 due Friday, 27-Oct at 4:00PM.
• Homework 5 due Monday, 13-Nov at 4:00PM.
• Homework 6 due Monday, 20-Nov at 4:00PM.
• Homework 7 due Friday, 1-Dec at 4:00PM.
• Homework 8 due Friday, 8-Dec at 4:00PM.
• Homework 8 Solutions

Exams:

• Midterm exam:
  In Gowen 301 at the regular class time on Friday, 3-Nov-2017. This will be open book and open notes, hard copies only. The coverage includes all topics through divide and conquer. An old sample midterm is available along with sample solutions.
  There will be a review session on Thursday, 2-Nov-2017 at 4:30 pm in MGH 241. Please bring your questions.
• Final exam:
  In Gowen 301 on Monday, 11-Dec-2017 at 4:30-6:20 pm as shown in the UW exam schedule. This will be open book and open notes, hard copies only. There is an old final exam and a practice final from previous offerings of the course. There are also solutions to the practice final. There will be a review session on Sunday, 10-Dec-2017 at 4:00 pm in our usual classroom, EEB 125. Please bring your questions.