Aug 23–27 
Administrivia and course goals
Introduction;
strings and induction
[scribbles,
video]

String induction
[induction notes]
[solutions]

Languages and regular expressions;
[scribbles,
video]

Regular expressions
[solutions]

Aug 30—Sep 3 
DFAs: intuition, definitions, examples
[scribbles,
video]

DFAs
[Automata Tutor,
JFLAP,
solutions]

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

DFA product construction
[solutions]

Sep 6–10 
Proving nonregularity via fooling sets
NFAs: intuition and examples
[scribbles, video]
[additional fooling set notes by Eric Huber]

Proving nonregularity
[solutions]

NFAs: εtransitions, equivalence with DFAs
[scribbles, video]

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

Sep 13–17 
Converting regular expressions to NFAs,
language transformations
[scribbles, video],
[language transformations walkthrough video pdf or notability]

Language transformations
[solutions]

Contextfree languages and grammars
[scribbles, video]

Contextfree grammars
[solutions]

Sep 20–24 
Turing machines

TBA
[solutions]

Optional review for Midterm 1

Optional review for Midterm 1

Midterm 1 — Monday, September 27, 7:00–9:30pm
Conflict exam: Tuesday, September 28

Sep 27–Oct 1 
Recursion: Hanoi, mergesort, quicksort

Hint: Binary search
[solutions]

Divide and conquer: Karatsuba multiplication, lineartime selection

Fun with Karatsuba
[solutions]

Oct 4–8 
Backtracking: n queens, game trees, text segmentation

Backtracking
[solutions]

Dynamic programming: Fibonacci, text segmentation again

Dynamic programming
[solutions]

Oct 11–15 
Sequence dynamic programming: Edit distance

More dynamic programming
[solutions]

Treeshaped dynamic programming: Optimal binary search trees

Yet even still more dynamic programming
[solutions]
Drop deadline

Oct 18–22 
Graphs: definitions, representations, data structures, traversal

Graph modeling
[solutions]

Depthfirst search, topological sort

Topological sort
[solutions]

Oct 25–29 
Dynamic programming in DAGs, strongly connected components
Generic shortest paths

Shortest paths
[solutions]

Shortest paths:
BFS, DFS, Disjktra, BellmanFord, and (briefly)
FloydWarshall

Allpairs shortest paths
[solutions]

Nov 1–5 
Allpairs shortest paths in detail

More graph modeling
[solutions]

Optional review for Midterm 2

Optional review for Midterm 2

Midterm 2 — Monday, November 8, 7:00–9:30pm
Conflict exam: Tuesday, November 9

Nov 8–12 
P vs NP, NPhardness, CookLevin Theorem, Circuit SAT, 3SAT
(♥
Removing nondeterminism via dovetailing, proof of CookLevin)

Selfreductions
[solutions]

NPhardness reductions: Independent Set, Clique, Vertex Cover, 3coloring

NPhardness proofs
[solutions]

Nov 15–19 
More NPhardness reductions: Hamiltonian cycle, choosing which problem to reduce from, international draughts

More NPhardness proofs
[solutions]

NPhardness review

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

Nov 22–26 
Thanksgiving break 
Nov 29—Dec 3 
Undecidability: code is data, the nonpresident's club, selfhaters gonna selfhate, halting problem

Undecidability via reductions
[solutions]

Undecidability: reductions and Rice's theorem

Using Rice's Theorem
[solutions]

Dec 6–10 
Wrapup and final exam review

Review for final exam 


Final exam — Wednesday, December 15, 8am—11am
Conflict exam: TBA
