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

Hint: Binary search

Divide and conquer: Karatsuba multiplication, lineartime selection

Fun with Karatsuba

Feb 26–Mar 2 
Backtracking: n queens, subset sum, longest increasing subsequence

Backtracking

Dynamic programming: Fibonacci, longest increasing subsequence

Dynamic programming

Mar 5–9 
Sequence dynamic programming

More dynamic programming

Treeshaped dynamic programming

Yet even still more dynamic programming
Drop deadline

Mar 12–16 
Greedy algorithms: tape sorting, scheduling, exchange arguments

Which greedy algorithm?

Graphs: definitions, representations, data structures, traversal

Graph modeling

Mar 19–23 
Spring break 
Mar 26–30 
Depthfirst search, topological sort

Topological sort

Strongly connected components
Greedy shortest paths: Dijkstra

Shortest paths

Apr 2–6 
Shortest paths via dynamic programming:
ShimbelMooreBellmanFord and
FloydRoyKleeneWarshall

Allpairs shortest paths

Optional review for Midterm 2

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
(♥
Removing nondeterminism via dovetailing, proof of CookLevin)

Selfreductions

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

NPhardness proofs

Apr 16–20 
More NPhardness reductions: 3coloring, Hamiltonian cycle

More NPhardness proofs

[Slack]

Return of the Son of Beneath the Planet of the NPHardness Proofs, the Final Chapter, Part II, Section 27B/6

Apr 23–27 
Undecidability: halting problem, diagonalization, reductions

Undecidability via reductions

Undecidability: more reductions, Rice's theorem
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
