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]
|
★
Context-free languages and grammars
[scribbles,
my video]
|
Context-free 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, linear-time 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]
|
★
Tree-shaped 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]
|
★
Depth-first 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:
Shimbel-Moore-Bellman-Ford and
Roy-Kleene-Floyd-Warshall
[scribbles,
my video]
|
All-pairs 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, NP-hardness, Cook-Levin Theorem, Circuit SAT, 3SAT, Independent Set
(♥
Removing nondeterminism via dovetailing, proof of Cook-Levin)
[scribbles,
my video]
|
Self-reductions
[solutions]
|
NP-hardness reductions: Clique, Vertex Cover, 3-coloring, Hamiltonian cycle
[scribbles,
my video]
|
NP-hardness proofs
[solutions]
|
Apr 16–20 |
More NP-hardness reductions: Hamiltonian cycle again, Super Mario Bros, international draughts
[scribbles,
my video]
|
More NP-hardness proofs
[solutions]
|
Undecidability: code is data, the non-president's club, diagonalization, self-haters gonna self-hate, 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 |
Wrap-up and Q&A |
Review for final |
|
|
Final exam — Tuesday, May 8, 8–11am
Conflict exam: TBA
|