- Submit written problem solutions to canvas, one PDF for each problem separately.
- Submit coding question solutions to the programming server.
Schedule
Click on the links to view the lecture notes.
(colors indicate weeks)
| Day |
Date |
Topic & Lecture Notes |
Other Handouts |
Homework |
| Th |
9/1 |
Fast integer multiplication
+ Sorting |
syllabus |
HW1, HW1 source |
| Tu |
9/6 |
Greedy Algorithms
(minimum spanning tree) |
Section 1
Master
thm
|
|
| Th |
9/8 |
Greedy Algorithms (cont.), Union-Find
Study Card Day |
|
HW2, HW2 source (figure)
HW1 due (Fri) |
| Tu |
9/13 |
Divide & Conquer |
Section 2 |
|
| Th |
9/15 |
Memoization / Dynamic Programming |
|
HW3, HW3 source
HW2 due (Fri) |
| Tu |
9/20 |
Models of Computation: RAMs |
Section 3 |
|
| Th |
9/22 |
Turing Machines |
|
HW4, HW4 source
HW3 due (Fri) |
| Tu |
9/27 |
Shortest Paths |
Section 4 |
|
| Th |
9/29 |
Linear programming |
|
HW5, HW5 source
HW4 due (Fri) |
| Tu |
10/4 |
Network flows and min-cut |
Section 5 |
|
| Th |
10/6 |
Finite Automata |
|
HW5 due (Fri) |
| Tu |
10/11 |
Midterm
| |
|
| Th |
10/13 |
Nondeterministic Finite Automata |
|
HW6, HW6 source |
| Tu |
10/18 |
Nondeterministic Poly-Time, P vs. NP |
Section 6 |
|
| Th |
10/20 |
NP-completeness |
|
HW7, HW7 source
HW6 due (Fri) |
| Tu |
10/25 |
Cook-Levin Thm, Ladner's theorem |
Section 7 |
|
| Th |
10/27 |
Ladner's theorem (cont.), Undecidability |
|
HW8, HW8 source
HW7 due (Fri) |
| Tu |
11/1 |
More Undecidability, and Godel's Incompleteness Theorem |
Section 8 |
|
| Th |
11/3 |
Randomness: QuickSort/Select and Freivalds' Algorithm |
|
HW9, HW9 source (figure)
HW8 due (Fri) |
| Tu |
11/8 |
Hashing |
Section 9 |
|
| Th |
11/10 |
Randomized Algorithms & Complexity |
|
HW10, HW10 source
HW9 due (Fri) |
| Tu |
11/15 |
Approximation algorithms |
Section 10 |
|
| Th |
11/17 |
Approximation algorithms |
|
HW11, HW11 source
HW10 due (Fri) |
| Tu |
11/22 |
PCP theorem, hardness of approximation, and parallel repetition |
PCP theorem history |
|
| Th |
11/24 |
Thanksgiving |
|
|
| Tu |
11/29 |
A weak PCP theorem |
Section 11 |
HW11 due (Wed) |
| Th |
12/1 |
Wrapup |
Final Review Notes |
|