#
Lecture Topics

*This schedule is tentative and may be subject to change.*

## 8/24 — Course introduction and Stable Matching I: Gale-Shapley algorithm

*Reading:* §1.1

(due Thursday, August 30th 11:59 PM)

## 8/27 — Stable matching II: Analysis of Gale–Shapley

*Reading:* §1.2

## 8/29 — Greedy Algorithms I: Interval Scheduling

*Reading:* §4.1

## 8/31 — Greedy Algorithms II: Minimizing Lateness

*Reading:* §4.2

(due Thursday, September 6th 11:59 PM)

##
9/3 —
*Labor Day, no class*

## 9/5 — Greedy Algorithms III: Minimum Spanning Tree

*Reading:* §4.5, 4.6

## 9/7 — Dynamic Programming I: Weighted Interval Scheduling

*Reading:* §6.1

(due Thursday, September 13th 11:59 PM)

## 9/10 — Dynamic Programming II: Segmented Least Squares

*Reading:* §6.3

## 9/12 — Dynamic Programming III: Sequence Alignment

*Reading:* §6.6

## 9/14 — Dynamic Programming IV: Shortest Path in a Graph

*Reading:* §6.8

(due Thursday, September 20th 11:59 PM)

## 9/17 — Dynamic Programming V: Knapsack

*Reading:* §6.4

## 9/19 — Divide and Conquer I: Integer Multiplication

*Reading:* § 5.1 and 5.5

## 9/21 — Divide and Conquer II (and Randomized Algorithms I): Median Finding

*Reading:* § 5.2 and 13.5

(due

**Tuesday, October 2nd**11:59 PM; no late days)

## 9/24 — Randomized Algorithms II: Random Variables Review and Hashing

*Reading:* §13.3, 13.6

## 9/26 — Randomized Algorithms III: More Hashing

*Reading:* §13.6

## 9/28 — Divide and Conquer III: Sequence Alignment in Linear Space

*Reading:* §6.7

## 10/1 — Randomized Algorithms IV: Prime Testing

*Reading:*
Supplementary Notes

## 10/3 — Network Flows I: Introduction

*Reading:* §7.1

## 10/5 — Network Flows II: Maximum Flows and Minimum Cuts

*Reading:* §7.2

##
10/8 —
*Fall Break, no class*

## 10/10 — Prelim Review

##
10/11, 7:30 PM —
**Prelim I: Stable Matching, Greedy Algorithms, Dynamic Programming,
Divide and Conquer, Randomized Algorithms**

## 10/12 — Network Flows III: Applications — Bipartite Matching

*Reading:* §7.5

(due Thursday, October 18th 11:59 PM)

## 10/15 — Network Flows IV: Extensions of the Max-Flow Problem

*Reading:* §7.7

## 10/17 — Network Flows V: Applications of Min Cuts — Image Segmentation

*Reading:* §7.10

## 10/19 — NP-Completeness I: Introduction to Hardness Reductions

*Reading:* §8.1

(due Thursday, October 25th 11:59 PM)

## 10/22 — NP-Completeness II: Reductions cont., SAT

*Reading:* §8.2

## 10/24 — NP-Completeness III: Defining NP and NP-Completeness

*Reading:* §8.3, 8.4

## 10/26 — NP-Completeness IV: The Traveling Salesman Problem

*Reading:* §8.5

(due Thursday, November 1st 11:59 PM -

**no late days**)

## 10/29 — NP-Completeness V: Subset Sum

*Reading:* §8.8 and Supplementary Notes

## 10/31 — NP-Completeness VI: NP and and other complexity classes

*Reading:* § 8.9

## 11/2 — Computability I: Defining Computability

*Reading:* Supplementary Notes, § 1-3

## 11/5 — Prelim Review

##
11/6, 7:30 PM —
**Prelim II: Network Flows and NP-Completeness**

## 11/7 — Computability II: Diagonalization and the Halting Problem

*Reading:* Supplementary Notes, § 4

## 11/9 — Computability III: Reductions to the Halting Problem and Rice's Theorem

*Reading:* Supplementary Notes, § 5-6

(due Thursday, November 15th 11:59 PM)

## 11/12 — Computability IV: Turing Machines and the Church-Turing Hypothesis

*Reading:* Supplementary Notes, § 7

## 11/14 — Computability V: SAT is NP-Complete

*Reading:* Supplementary Notes, § 8

## 11/16 — Approximation Algorithms I: Greedy Algorithms

*Reading:* Introduction to Chapter §11,
Greedy Approximation Algorithms notes

(due

**Thursday, November 29th**11:59 PM)

## 11/19 — Approximation Algorithms II: Knapsack

*Reading:*§11.8

##
11/21-23 —
*Thanksgiving Break, no class*

## 11/26 — Approximation Algorithms III: Using Linear Programming

*Reading:* §11.6

## 11/28 — Online Algorithms I: Online Matching

*Reading:*
Online Matching Algorithm notes

## 11/30 — Online Algorithms II: Caching

*Reading:* §13.8

## 12/3 — Algorithms and Selfish Users

*Reading:* §12.7