Aug 26–30 
Administrivia and course goals
Introduction and history;
strings
[scribbles,
my video]

String induction
[induction notes]
[solutions]

String induction,
Languages and regular expressions
[scribbles,
my video]

Regular expressions
[solutions]

Sep 2–6 
DFAs: intuition, definitions, examples
[Automata Tutor,
JFLAP,
scribbles,
my video]

DFA construction
[Automata Tutor,
JFLAP,
solutions]

DFAs: product construction, closure properties, automatic=regular, fooling sets
[scribbles,
my video]

DFA product construction
[solutions]

Sep 9–13 
Proving nonregularity via fooling sets
NFAs: intuition and examples
[scribbles,
Echo360 video]

Proving nonregularity
[solutions]

NFAs: εtransitions, (most of) equivalence with DFAs and regular expressions
[scribbles,
my video]

Regex to NFA to DFA (to regex)
[solutions]

Sep 16–20 
Converting NFAs to regular expressions,
language transformations
[Chandra's slides]

Language transformations
[solutions]

Contextfree languages and grammars
[Ian's slides]

Contextfree grammars
[solutions]

Sep 23–27 
Turing machines
[scribbles,
my video]

Language transformation formalism
[solutions]

Optional review for Midterm 1
[fake midterm,
scribbles,
my video]

Optional review for Midterm 1

Midterm 1 — Monday, September 30, 7–9pm
Conflict exam: Tuesday, October 1

Sep 30–Oct 4 
Recursion: Hanoi, mergesort, quicksort
[scribbles,
my video]

Hint: Binary search
[solutions]

Divide and conquer: Karatsuba multiplication, lineartime selection
[scribbles,
my video]

Fun with Karatsuba
[solutions]

Oct 7–11 
Backtracking: n queens, game trees, text segmentation
[scribbles,
my video]

Backtracking
[solutions]

Dynamic programming: Fibonacci, text segmentation again
[scribbles,
my video]

Dynamic programming
[solutions]

Oct 14–18 
Sequence dynamic programming: Edit distance
[scribbles,
my video]

More dynamic programming
[solutions]

Treeshaped dynamic programming: Optimal binary search trees
[scribbles,
my video]

Yet even still more dynamic programming
[solutions]
Drop deadline

Oct 21–25 
Graphs: definitions, representations, data structures, traversal
[scribbles,
my video]

Graph modeling
[solutions]

Depthfirst search, topological sort
[scribbles,
my video]

Topological sort
[solutions]

Oct 28–Nov 1 
Dynamic programming in DAGs, strongly connected components
Generic shortest paths
[scribbles,
my video]

Shortest paths
[solutions]

Shortest paths:
BFS, DFS, Disjktra, BellmanFord, and (briefly)
FloydWarshall
[scribbles,
my video]

Allpairs shortest paths
[solutions]

Nov 4–8 
Allpairs shortest paths in detail
[scribbles,
my video]

More graph modeling
[solutions]

Optional review for Midterm 2
[fake midterm,
scribbles,
my video,
extra video for problem 4]

Optional review for Midterm 2

Midterm 2 — Monday, November 11, 7–9pm
Conflict exam: Tuesday, November 12

Nov 11–15 
P vs NP, NPhardness, CookLevin Theorem, Circuit SAT, 3SAT
(♥
Removing nondeterminism via dovetailing, proof of CookLevin)
[blackboard,
Echo360 video]

Selfreductions
[solutions]

NPhardness reductions: Independent Set, Clique, Vertex Cover, 3coloring
[scribbles,
my video]

NPhardness proofs
[solutions]

Nov 18–22 
More NPhardness reductions: Hamiltonian cycle, choosing which problem to reduce from, international draughts
[scribbles,
my video]

More NPhardness proofs
[solutions]

NPhardness review
[scribbles,
my video]

Return of the Son of Revenge of the Planet of the NPhardness Proofs, the Final Chapter, Part 4½: Zatoichi versus Godzilla
[solutions]

Nov 25–29 
Thanksgiving break 
Dec 2–6 
Undecidability: code is data, the nonpresident's club, selfhaters gonna selfhate, halting problem
[scribbles,
my video]
< 
Undecidability via reductions
[solutions]

Undecidability: reductions and Rice's theorem
ICES Forms
[scribbles,
my video]

Using Rice's Theorem
[solutions]
TA ICES Forms

Dec 9–13 
Wrapup and final exam review
[scribbles,
my video]

Review for final exam 

Final Exam 
Final exam — Friday, December 13, 8am–11am
Conflict exam: TBA
