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, reductions

Undecidability via reductions
[solutions]

Apr 23β27 
Undecidability: more reductions, Rice's theorem

Using Rice's Theorem

Universal models of computation
ICES Forms

Using Rice's Theorem
TA ICES Forms

Apr 30βMay 4 
Wrapup and preliminary review for the final exam 
Review for final 


Final exam β Tuesday, May 8, 8β11am
Conflict exam: TBA
