Jan 15–19 
Administrivia and course goals
Introduction and history;
★ strings
[scribbles,
my video]

String induction
[induction notes]
[solutions]

★ Languages and regular expressions
[scribbles,
my video]

Regular expressions
[solutions]

Jan 22–26 
★
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]

Jan 29–Feb 2 
★
Proving nonregularity via fooling sets
NFAs: intuition and examples
[scribbles,
my 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]

Feb 5–9 
★
Converting NFAs to regular expressions,
language transformations
[scribbles,
my video]

Language transformations
[solutions]

★
Contextfree languages and grammars
[scribbles,
my video]

Contextfree grammars
[solutions]

Feb 12–16 
Turing machines
[scribbles,
my video]

Language transformation formalism
[solutions]

Optional review for Midterm 1
[scribbles,
my video]

Optional review for Midterm 1

Midterm 1 — Monday, February 19, 7–9pm
Conflict exam: Tuesday, February 20

Feb 19–23 
★
Recursion: Hanoi, mergesort
[scribbles,
my video]

Hint: Binary search
[solutions]

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

Fun with Karatsuba
[solutions]

Feb 26–Mar 2 
★
Backtracking: n queens, game trees, text segmentation
[scribbles,
my video]

Backtracking
[solutions,
scribbles,
video: intro,
#1,
#1 again,
#2,
#3]

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

Dynamic programming
[solutions,
scribbles,
video: #1,
#1 again,
#2,
#3,
#5]

Mar 5–9 
★
Sequence dynamic programming: Edit distance
[scribbles,
my video]

More dynamic programming
[solutions,
scribbles,
video: #1,
#2,
#3]

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

Yet even still more dynamic programming
[solutions,
scribbles,
video: #1,
#2a,
#2b]

Mar 12–16 
★
Graphs: definitions, representations, data structures, traversal
[scribbles,
my video]

Graph modeling
[solutions]

★
Depthfirst search, topological sort
[scribbles,
my video]

Topological sort
[solutions]
Drop deadline

Mar 19–23 
Spring break 
Mar 26–30 
★
Strongly connected components
Greedy shortest paths: Dijkstra
[scribbles,
my video]

Shortest paths
[solutions]

Shortest paths via dynamic programming:
ShimbelMooreBellmanFord and
RoyKleeneFloydWarshall
[scribbles,
my video]

Allpairs shortest paths
[solutions]

Apr 2–6 
★
Minimum spanning trees
[scribbles,
my video]

More graph modeling
[solutions]

Optional review for Midterm 2
[scribbles,
my video]

Optional review for Midterm 2

Midterm 2 — Monday, April 9, 7–9pm
Conflict exam: Tuesday, April 10

Apr 9–13 
P vs NP, NPhardness, CookLevin Theorem, Circuit SAT, 3SAT, Independent Set
(♥
Removing nondeterminism via dovetailing, proof of CookLevin)
[scribbles,
my video]

Selfreductions
[solutions]

NPhardness reductions: Clique, Vertex Cover, 3coloring, Hamiltonian cycle
[scribbles,
my video]

NPhardness proofs
[solutions]

Apr 16–20 
More NPhardness reductions: Hamiltonian cycle again, Super Mario Bros, international draughts
[scribbles,
my video]

More NPhardness proofs
[solutions]

Undecidability: code is data, the nonpresident's club, diagonalization, selfhaters gonna selfhate, halting problem
[scribbles,
my video: #1 #2]

Undecidability via reductions
[solutions]

Apr 23–27 
Undecidability: reductions, Rice's theorem
[scribbles,
my video]

Using Rice's Theorem
[solutions]

Undecidability: Proof of Rice's theorem
Universal models of computation
[scribbles,
my video]
ICES Forms

More undecidability
[solutions]
TA ICES Forms

Apr 30–May 4 
Wrapup and Q&A 
Review for final 


Final exam — Tuesday, May 8, 8–11am
Conflict exam: TBA
