Aug 25–29 
Administrivia and course goals
♺
Introduction and history
[video]

Induction boilerplate
(♺ induction notes)

✍ Strings, string functions, and
✍ languages
[video]

String induction

Sep 1–5 
✍ Regular expressions and
✍ contextfree grammars
[video]

Regular expressions

✍ DFAs: definitions, examples, intuition
[video]

Contextfree grammars

Sep 8–12 
✍ DFAs: design techniques, product construction, closure properties of regular languages
[video]

DFA construction

✍
Proving nonregularity via fooling sets
Nondeterminism: intuition, examples, NFA definitions
[video]

Proving nonregularity

Sep 15–19 
✍
NFAs: εtransitions, generalizations, equivalence with DFAs and regular expressions
[video]

Regular or not?
(End of Midterm 1 material) 
★
Recursion: Hanoi, mergesort
[video]

Hint: binary search

Sep 22–26 
★
Recursion: lineartime selection, Karatsuba multiplication
[video]
(♺
notes on recurrences)

Optional review for Midterm 1 
Midterm 1, 7–9pm (No lecture)
[video of review session]

More recursion

Sep 29–Oct 3 
★
Backtracking: n queens, subset sum, NFA acceptance, longest increasing subsequence
[video]

Backtracking

★
Dynamic programming: Fibonacci, longest increasing subsequence
[video]

Dynamic programming 
Oct 6–10 
★
Dynamic programming: subset sum, NFA acceptance, edit distance
[video] 
More dynamic programming 
★
Treelike dynamic programming: Parsing contextfree languages
[video] 
Return of the son of revenge of dynamic programming, the final chapter, part III: Zatoichi versus Godzilla 
Oct 13–17 
♺
Greedy algorithms: tape sorting, scheduling, exchange arguments
[video] 
Which greedy algorithm? 
★
Graphs: definitions, representations, data structures, whateverfirst search
[video]/td>

Graph modeling
Drop deadline 
Oct 20–24 
♺
Depthfirst search, topological sort
[video] 
Graph modeling 
♺
Minimum spanning trees: Borůvka and, if you absolutely insist, two others
[video] 
Minimum spanning trees 
Oct 27–31 
♺
Singlesource shortest paths: Dijkstra, BellmanFord
[video]
(♥★
Allpairs shortest paths: FloydKleeneWarshall)

Shortest paths
(End of Midterm 2 material) 
✍
Turing machines: history, formal definitions, examples
[video]
(See also Lenny's slides from last semester) 
Turing machine design, costumes, candy 
Nov 3–7 
✍Turing machine variations: multiple tracks, heads, and tapes; doublyinfinite tape; subroutines; randomaccess memory
[video]
(See also Lenny's slides from last semester) 
Optional review for Midterm 2 
Midterm 2, 7–9pm (No lecture)
[video of review session] 
Wacky machine design 
Nov 10–14 
✍ Nondeterminism, dovetailing
[video]
(See also Lenny's slides from last semester) 
deciding TM behavior 
♺
P vs NP, NPhardness, CookLevin Theorem, circuit and formula satisfiability
[video]
(
♥✍
Proof of the CookLevin theorem)

Selfreduction 
Nov 17–21 
♺
NPhardness reductions: 3SAT, Independent Set, Clique, Vertex Cover
[video] 
NPhardness proofs 
♺
More NPhardness reductions: 3coloring, Hamiltonian cycle, international draughts
[video] 
More NPhardness proofs 
Nov 24–28 
Thanksgiving break 
Dec 1–5 
✍
Undecidability: diagonalization, reductions, halting problem
[video] 
Undecidability via reductions 
✍
Undecidability: reductions again, Rice's theorem
[video]
ICES Forms 
Using Rice's Theorem
ICES Forms 
Dec 8–12 
Wrapup — Any questions?
[video] 
Review for final 
Dec 15–19 
Final exam: 7–10pm 