 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.), UnionFind
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 mincut 
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 PolyTime, P vs. NP 
Section 6 

Th 
10/20 
NPcompleteness 

HW7, HW7 source HW6 due (Fri) 
Tu 
10/25 
CookLevin 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 
