Aug 22–26 
Administrivia and course goals
Introduction and history;
strings
[slides] [sorry, no video]

String induction
[induction notes]
[solutions]

★
Languages and regular expressions
[slides]
[video]

Regular expressions
[solutions]

Aug 29–Sep 2 
★
DFAs: intuition, definitions, examples
[Automata Tutor]
[slides]
[audio]

DFA construction
[solutions]

★
DFAs: design techniques, product construction, operations on regular languages
[slides]
[video]

DFA product construction
[solutions]

Sep 5–9 
★
Proving nonregularity via fooling sets
Nondeterminism: intuition, examples, NFA definitions
[slides]
[video]

Proving nonregularity
[solutions]

★
NFAs: εtransitions, equivalence with DFAs and regular expressions
[slides]
[video]

DFA/NFA transformation
[solutions]

Sep 12–16 
★
Contextfree languages and grammars
[slides]
[video]

Contextfree grammars
[solutions]

★
Turing machines: history, formal definitions, examples
[slides]
[video]

Regular or not?
[solutions]

Sep 19–23 
★
Turing machine variations: multiple tracks, heads, and tapes; doublyinfinite tape; subroutines; randomaccess memory
[slides]
[video]

Turing machine design
[solutions]

Optional review for Midterm 1

Optional review for Midterm 1

Midterm 1 — Monday, September 26, 7–9pm
Conflict exam: Tuesday, September 27

Sep 26–30 
★
Recursion: Hanoi, mergesort
[slides]
[video]

Hint: Binary search
[solutions]

★
Divide and conquer: lineartime selection, Karatsuba multiplication
[recurrence notes]
[slides]
[video]

Divide and conquer
[solutions]

Oct 3–7 
★
Backtracking: n queens, subset sum, longest increasing subsequence
[slides]
[borked video]

Backtracking
[solutions]

★
Dynamic programming: Fibonacci, longest increasing subsequence
[slides]
[video]

Dynamic programming
[solutions]

Oct 10–14 
★
Sequence dynamic programming
[slides: pdf, note]
[video]

More dynamic programming
[solutions]

★
Treeshaped dynamic programming
[slides: pdf, note]
[video]

Yet even still more dynamic programming
Drop deadline
[solutions]

Oct 13–21 
★
Greedy algorithms: tape sorting, scheduling, exchange arguments
[slides]
[video]

Which greedy algorithm?
[solutions]

★
Graphs: definitions, representations, data structures, traversal
[slides]
[video]

Graph modeling
[solutions]

Oct 24–28 
★
Depthfirst search, topological sort
[slides]
[video]

Topological sort
[solutions]

★
Strongly connected components
Greedy shortest paths: Dijkstra
[slides]
[video]

Shortest paths
[solutions]

Oct 31–Nov 4 
Shortest paths via dynamic programming:
ShimbelMooreBellmanFord and
FloydRoyKleeneWarshall
[slides]
[video]

Allpairs shortest paths
[solutions]

Optional review for Midterm 2

Optional review for Midterm 2

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

Nov 7–11 
★
P vs NP, NPhardness, CookLevin Theorem
(♥
Removing nondeterminism via dovetailing, proof of CookLevin)
[slides]
[video]

Selfreductions
[solutions]

★
NPhardness reductions: 3SAT, Independent Set, Clique, Vertex Cover
[slides]
[video]

NPhardness proofs
[solutions]

Nov 14–18 
★
More NPhardness reductions: 3coloring, Hamiltonian cycle
[slides]
[video]

More NPhardness proofs
[solutions]

♥
Approximation algorithms, hardness of approximation, unique games
[video]

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

Nov 21–25 
Thanksgiving break 
Nov 29–Dec 2 
★
Undecidability: halting problem, diagonalization, reductions
[slides]
[video]

Undecidability via reductions
[solutions]

★
Undecidability: more reductions, Rice's theorem
ICES Forms
[slides]
[video]

Using Rice's Theorem
ICES Forms
[solutions]

Dec 5–9 
Wrapup and preliminary review for the final exam 
Review for final 


Final exam — Thursday, December 15, 7–10pm
Conflict exam: TBA
