Course Schedule

Homework is due at the start of class on the specified due date.

This is a tentative schedule, which is almost certain to change. Check this web page frequently for adjustments made during the semester.

KT = Readings from Algorithm Design by Kleinberg and Tardos

Mon Tue Wed Thu Fri
  22Aug

Introduction and Course Overview
23Aug
24Aug

Implementing Stable Matching

KT 1.1, 2.3

Python Reading

Python Code from Lecture
25Aug
28Aug
29Aug

Algorithm Analysis I

KT 1.2, 2.1-2.2
30Aug
31Aug

Algorithm Analysis II

Python Pass by Object Reference Model

KT 2.4-2.5
01Sep
04Sep
Labor Day
05Sep

Graphs in Python, and Induction-based Topological Sort

Python code from Lecture

KT 3.1, 3.6
06Sep
07Sep

DFS and BFS Graph Traversal

Traversal Code

KT 3.2

HW1 due

HW1 starter code
08Sep
11Sep
12Sep

AVL trees

Reading

AVL Insert Handout
13Sep
14Sep

B trees

Handout
15Sep
18Sep
19Sep

No Class
20Sep
21Sep

Greedy: Coin Changing, Interval Scheduling, Interval Partitioning

Interval Scheduling Demo

Interval Partitioning Demo

KT 4.1
22Sep

HW2 due

HW2 starter code

Python Package Installation Advice (for HW2)
25Sep
26Sep

Greedy: Shortest paths in weighted graphs (SP-DAG, Dijkstra)

KT 4.4
27Sep
28Sep

Midterm 1 Topics
29Sep
02Oct
03Oct

Midterm 1
04Oct
05Oct

Greedy: Huffman Codes

Code from Lecture

KT 4.8
06Oct
09Oct
10Oct

Divide-Conquer: Mergesort and Counting Inversions

KT 5.1, 5.3

Handout

HW3 Q1 helper code
11Oct
12Oct

Divide-Conquer: Quickselect, quicksort and master theorem
13Oct

HW3 due
16Oct
17Oct

Hashing
18Oct
19Oct

Dynamic Programming: Motivation, memoization, weighted interval scheduling

KT 6.1-2
20Oct
23Oct
24Oct

Dynamic Programming: Knapsack

KT 6.4

HW4 due

HW4 starter code
25Oct
26Oct

Midterm Review

Midterm 2 Topics
27Oct
30Oct
31Oct

Branch and Bound (Wainwright)
01Nov
02Nov

Midterm 2
03Nov
06Nov
07Nov

Dynamic Programming: Edit distance
08Nov
09Nov

Dynamic Programming: Edit distance
10Nov
13Nov
14Nov

Intractability: Reductions

KT 8.1-2
15Nov
16Nov
17Nov
20Nov
Thanksgiving Break
21Nov
Thanksgiving Break
22Nov
Thanksgiving Break
23Nov
Thanksgiving Break
24Nov
Thanksgiving Break
27Nov
28Nov

Intractability: P, NP, NP-complete

KT 8.3-8.5

HW5 due
29Nov
30Nov

Final Exam Review
01Dec
04Dec

Last day of classes
05Dec

Reading period
06Dec

Reading period
07Dec
08Dec

Final Exam (1pm-3:25pm)
11Dec
12Dec
13Dec
14Dec
15Dec