Aug 2831 
Administrivia and course goals
Notes on strings
[sect A: slides1, slides2] [sect B: slides1, slides2] 
String induction
[Jeff's induction notes, Chandra's additional notes] [solutions] 
Languages and regular expressions [sec A slides, sect B slides] 
Regular expressions
[solutions] 
Sep 47 
DFAs, product construction
[Automata Tutor] [sec A slides] [sec B slides] DFA Proofs 
DFA construction
[solutions] 
Nondeterminism, NFAs
Jeff's NFA notes
[sec A slides] [sec B slides] 
DFA product construction
[solutions] 
Sep 1114 
NFAs continued, equivalence with DFAs and regular expressions
Jeff's NFA notes
[sec A slides sec B slides] 
DFA/NFA transformation
[solutions] 
Proving nonregularity via fooling sets
[slides]
[DFA Proofs][Fooling sets guide] 
Proving nonregularity
[solutions] 
Sep 1821 
Contextfree languages and grammars
[slides: secA, secB]

Contextfree grammars
[solutions] 
Turing machines: history, formal definitions, examples, variations
[slides]

Regular or not?
[solutions] 
Sep 2528 
Universal Turing Machine, RAM simulation, P
[UTM slides][complexity slides]

Turing machine design
[solutions] 
SecA Optional review for Midterm 1
Sec B Recursion: Hanoi, mergesort (see Oct 2 links)
sec B slides
 Optional review for Midterm 1 
Midterm 1: Monday, October 1, 79:30pm

Oct 25 
Sec A: Recursion: Hanoi, mergesort
Sec B: no lecture
[slides][solving recurrences]

Hint: Binary search
[solutions] 
Divide and conquer: lineartime selection, Karatsuba multiplication
[recurrence notes] [slides]

Divide and conquer
[solutions] 
Oct 912 
Backtracking: independent set, longest increasing subsequence
[sec A slides sec B notebook] 
Backtracking
[solutions] 
Dynamic programming: splitting strings, longest increasing subsequence
[slides sec B notebook] 
Dynamic programming
[solutions] 
Oct 1619 
More DP: Edit Distance, MIS in trees
[slides]

More dynamic programming
[solutions] 
CYK Algorithm, Graphs, basic search
[CYK slides, Graph search slides] 
Yet even still more dynamic programming
Drop deadline
[solutions] 
Oct 2326 
Directed graphs, depthfirst search
[slides]

Graph modeling
[solutions] 
Catch up lecture
[Graph notes]

Graph modeling
[solutions] 
Oct 30  Nov 2 
BFS and Shortest Paths
[slides]

Shortest paths
[solutions] 
Shortest Paths with Negative Lengths via DP
[slides]

More shortest paths
[solutions] 
Nov 69 
MST Algorithms
[Kent's slides], [slides]

MST
[solutions] 
Optional review for midterm 2
[sec B sketches] 
Optional review for Midterm 2 
Midterm 2: Monday, November 12, 79:30pm
Conflict exam: Tuesday, Nove 13 
Nov 1316 
Greedy algorithms
[slides]
 Greedy
[solutions] 
Undecidability: halting problem, diagonalization, reductions
[slides]

Undecidability via reductions
[solutions] 
Nov 2023 
Fall break 
Nov 2730 
Polynomial time Reductions
[slides]

Self Reductions
[solutions] 
NP, NPCompleteness,
3SAT to Independent Set
[slides][helpful video on P vs NP] 
NPhardness proofs
[solutions] 
Dec 47 
More NPhardness reductions: 3coloring, Hamiltonian cycle
[slides]

NPHardness, the final chapter
[solutions] 
Undecidability: more reductions, Rice's theorem
[slides]
ICES Forms 
Using Rice's Theorem
ICES Forms
[solutions] 
Dec 1114 
No lecture, review session Thursday 
Review for final 
Review session: 7pm, ECEB 1002 

Final exam: Saturday, Dec 15, 1:304:30 p.m.
