Aug 25–29 |
Administrivia and course goals
♺
Introduction and history
[video]
|
Induction boilerplate
(♺ induction notes)
|
✍ Strings, string functions, and
✍ languages
[video]
|
String induction
|
Sep 1–5 |
✍ Regular expressions and
✍ context-free grammars
[video]
|
Regular expressions
|
✍ DFAs: definitions, examples, intuition
[video]
|
Context-free grammars
|
Sep 8–12 |
✍ DFAs: design techniques, product construction, closure properties of regular languages
[video]
|
DFA construction
|
✍
Proving nonregularity via fooling sets
Nondeterminism: intuition, examples, NFA definitions
[video]
|
Proving nonregularity
|
Sep 15–19 |
✍
NFAs: ε-transitions, generalizations, equivalence with DFAs and regular expressions
[video]
|
Regular or not?
(End of Midterm 1 material) |
★
Recursion: Hanoi, mergesort
[video]
|
Hint: binary search
|
Sep 22–26 |
★
Recursion: linear-time selection, Karatsuba multiplication
[video]
(♺
notes on recurrences)
|
Optional review for Midterm 1 |
Midterm 1, 7–9pm (No lecture)
[video of review session]
|
More recursion
|
Sep 29–Oct 3 |
★
Backtracking: n queens, subset sum, NFA acceptance, longest increasing subsequence
[video]
|
Backtracking
|
★
Dynamic programming: Fibonacci, longest increasing subsequence
[video]
|
Dynamic programming |
Oct 6–10 |
★
Dynamic programming: subset sum, NFA acceptance, edit distance
[video] |
More dynamic programming |
★
Tree-like dynamic programming: Parsing context-free languages
[video] |
Return of the son of revenge of dynamic programming, the final chapter, part III: Zatoichi versus Godzilla |
Oct 13–17 |
♺
Greedy algorithms: tape sorting, scheduling, exchange arguments
[video] |
Which greedy algorithm? |
★
Graphs: definitions, representations, data structures, whatever-first search
[video]/td>
|
Graph modeling
Drop deadline |
Oct 20–24 |
♺
Depth-first search, topological sort
[video] |
Graph modeling |
♺
Minimum spanning trees: Borůvka and, if you absolutely insist, two others
[video] |
Minimum spanning trees |
Oct 27–31 |
♺
Single-source shortest paths: Dijkstra, Bellman-Ford
[video]
(♥★
All-pairs shortest paths: Floyd-Kleene-Warshall)
|
Shortest paths
(End of Midterm 2 material) |
✍
Turing machines: history, formal definitions, examples
[video]
(See also Lenny's slides from last semester) |
Turing machine design, costumes, candy |
Nov 3–7 |
✍Turing machine variations: multiple tracks, heads, and tapes; doubly-infinite tape; subroutines; random-access memory
[video]
(See also Lenny's slides from last semester) |
Optional review for Midterm 2 |
Midterm 2, 7–9pm (No lecture)
[video of review session] |
Wacky machine design |
Nov 10–14 |
✍ Nondeterminism, dovetailing
[video]
(See also Lenny's slides from last semester) |
deciding TM behavior |
♺
P vs NP, NP-hardness, Cook-Levin Theorem, circuit and formula satisfiability
[video]
(
♥✍
Proof of the Cook-Levin theorem)
|
Self-reduction |
Nov 17–21 |
♺
NP-hardness reductions: 3SAT, Independent Set, Clique, Vertex Cover
[video] |
NP-hardness proofs |
♺
More NP-hardness reductions: 3-coloring, Hamiltonian cycle, international draughts
[video] |
More NP-hardness proofs |
Nov 24–28 |
Thanksgiving break |
Dec 1–5 |
✍
Undecidability: diagonalization, reductions, halting problem
[video] |
Undecidability via reductions |
✍
Undecidability: reductions again, Rice's theorem
[video]
ICES Forms |
Using Rice's Theorem
ICES Forms |
Dec 8–12 |
Wrap-up — Any questions?
[video] |
Review for final |
Dec 15–19 |
Final exam: 7–10pm |