CS125 FALL 2016


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


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