Aug 23–27 |
Administrivia and course goals
Introduction;
strings and induction
[scribbles,
video]
|
String induction
[induction notes]
[solutions]
|
Languages and regular expressions;
[scribbles,
video]
|
Regular expressions
[solutions]
|
Aug 30–Sep 3 |
DFAs: intuition, definitions, examples
[scribbles,
video]
|
DFAs
[Automata Tutor,
JFLAP,
solutions]
|
DFAs: product construction, closure properties, automatic=regular
[scribbles,
video]
|
DFA product construction
[solutions]
|
Sep 6–10 |
Proving nonregularity via fooling sets
NFAs: intuition and examples
[scribbles, video]
[additional fooling set notes by Eric Huber]
|
Proving nonregularity
[solutions]
|
NFAs: ε-transitions, equivalence with DFAs
[scribbles, video]
|
Regex to NFA to DFA (to regex)
[solutions]
|
Sep 13–17 |
Converting regular expressions to NFAs,
language transformations
[scribbles, video],
[language transformations walkthrough video pdf or notability]
|
Language transformations
[solutions]
|
Context-free languages and grammars
[scribbles,
video]
|
Context-free grammars
[solutions]
|
Sep 20–24 |
Turing machines
[scribbles,
video]
|
More language transformations
[solutions]
|
Optional review for Midterm 1
[practice midterm,
Dakshita's solutions,
Jeff's solutions,
video]
|
Optional review for Midterm 1
|
Midterm 1 — Monday, September 27, 7:00–9:30pm
Conflict exam: Tuesday, September 28
|
Sep 27–Oct 1 |
Recursion: Hanoi, mergesort, quicksort
[scribbles,
video]
|
Hint: Binary search
[solutions]
|
Divide and conquer: Karatsuba multiplication, linear-time selection
[scribbles,
video]
|
Fun with Karatsuba
[solutions]
|
Oct 4–8 |
Backtracking: n queens, game trees, text segmentation
[scribbles,
video]
|
Backtracking
[solutions]
|
Dynamic programming: Fibonacci, text segmentation again
[scribbles,
video]
|
Dynamic programming
[solutions]
|
Oct 11–15 |
Sequence dynamic programming: Edit distance
[scribbles,
video]
|
More dynamic programming
[solutions]
|
Tree-shaped dynamic programming: Optimal binary search trees
[scribbles,
video]
|
Yet even still more dynamic programming
[solutions]
Drop deadline
|
Oct 18–22 |
Graphs: definitions, representations, data structures, traversal
[scribbles,
video]
|
Graph modeling
[solutions]
|
Depth-first search, topological sort
[scribbles,
video]
|
Topological sort
[solutions]
|
Oct 25–29 |
Dynamic programming in DAGs, strongly connected components
Generic shortest paths
[scribbles,
video]
|
Shortest paths
[solutions]
|
Shortest paths:
BFS, DFS, Disjktra, Bellman-Ford, and (briefly)
Floyd-Warshall
[scribbles,
video]
|
All-pairs shortest paths
[solutions]
|
Nov 1–5 |
All-pairs shortest paths in detail
[scribbles,
video]
|
Solve it both ways
[solutions]
|
Optional review for Midterm 2
[practice midterm,
Jeff's solutions,
video]
|
Optional review for Midterm 2
|
Midterm 2 — Monday, November 8, 7:00–9:30pm
Conflict exam: Tuesday, November 9
|
Nov 8–12 |
Reductions, hardness
[scribbles,
video]
|
Reductions
[solutions]
|
P vs NP, NP-hardness, NP-hardness reductions: 3SAT, Clique
[scribbles,
video]
|
NP-hardness proofs
[solutions]
|
Nov 15–19 |
More NP-hardness: 3 Coloring, Hamiltonian cycle
[scribbles,
video]
|
More NP-hardness proofs
[solutions]
|
Hamiltonian Cycle wrap-up, Hamiltonian path, other NP hard problems, NP-hardness review
[scribbles,
video]
|
Even more NP-hardness proofs
[solutions]
|
Nov 22–26 |
Thanksgiving break |
Nov 29–Dec 3 |
NP Hardness examples, Undecidability: code is data, the halting problem
[scribbles,
video]
ICES forms available
|
Yet even still more NP-hardness examples
[solutions]
|
Undecidability: reductions and Rice's theorem
[scribbles,
video,
skipped lab on undecidability reductions,
skipped lab solutions
|
Using Rice's Theorem
[solutions]
|
Dec 6–10 |
Wrap-up and final exam review
[scribbles,
video]
|
Review for final exam
ICES deadline
|
|
|
Final exam — Wednesday, December 15, 8am—11am
Conflict exam: TBA
|