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 |
★
Context-free languages and grammars
[slides]
[video]
|
Context-free 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; doubly-infinite tape; subroutines; random-access 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: linear-time 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]
|
★
Tree-shaped 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 |
★
Depth-first 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:
Shimbel-Moore-Bellman-Ford and
Floyd-Roy-Kleene-Warshall
[slides]
[video]
|
All-pairs 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, NP-hardness, Cook-Levin Theorem
(♥
Removing nondeterminism via dovetailing, proof of Cook-Levin)
[slides]
[video]
|
Self-reductions
[solutions]
|
★
NP-hardness reductions: 3SAT, Independent Set, Clique, Vertex Cover
[slides]
[video]
|
NP-hardness proofs
[solutions]
|
Nov 14–18 |
★
More NP-hardness reductions: 3-coloring, Hamiltonian cycle
[slides]
[video]
|
More NP-hardness proofs
[solutions]
|
♥
Approximation algorithms, hardness of approximation, unique games
[video]
|
Return of the Son of Beneath the Planet of the NP-Hardness 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 |
Wrap-up and preliminary review for the final exam |
Review for final |
|
|
Final exam — Thursday, December 15, 7–10pm
Conflict exam: TBA
|