|
Week 1: Aug 26-30
|
L1:Adminis+
trivia and course goals
Introduction and history;
strings
[slides1,
slides2
: scribbles]
|
String induction
[induction notes,
more]
[solutions]
|
L2:
Languages and regular expressions
[slides
:
scribbles]
|
Regular expressions
[solutions]
|
|
Week 2: Sep 2-6
|
L3:
DFAs, product construction
[Automata Tutor]
DFA Proofs
L3: [slides :
scribbles]
|
DFA construction
[solutions]
|
L4:
Non-determinism, NFAs
Jeff's NFA notes
L4: [slides]
|
DFA product construction
[solutions]
[ms : ct] |
|
Week 3: Sep 9-13
|
L5:
NFAs continued, equivalence with DFAs and
regular expressions
Jeff's NFA notes
Converting NFA
to regex
L5:
[slides
:
scribbles]
|
DFA/NFA transformation
[solutions]
|
L6:
Proving non-regularity via fooling sets
[DFA Proofs]
[Fooling
sets guide]
L6:
[slides
:
scribbles
:
h]
|
Proving non-regularity
[solutions]
|
|
Week 4: Sep 16-20
|
L7: Context-free languages and grammars
[slides
: scribbles]
|
Context-free grammars
[h]
[solutions]
|
L8:
More on
Context-free languages and grammars,
Turing
machines
L7:
[slides,
slides
: scribbles]
|
Regular or not?
[h]
[solutions]
|
|
Week 5: Sep 23-27
|
L9:
Halting and undecidability
L9: [slides]
|
Algorithms for langs
[solutions]
|
Optional review for Midterm 1
|
Optional review
for Midterm 1
|
|
Week 6: Sep 30-Oct 4
|
| Midterm 1: Monday, 7pm-9:30pm
(details):
solution.
|
L10:
Recursion: Hanoi,
mergesort
[slides
: scribbles]
[solving recurrences]
closest_pair.jl
|
Hint: Binary search
[solutions]
|
L11:
Divide and conquer: linear-time selection,
Karatsuba multiplication
[recurrence notes]
[slides
: scribbles]
|
Divide and conquer
[solutions]
|
|
Week 7: Oct 7-Oct 11
|
L12:
Backtracking:
independent set, longest increasing subsequence
[slides
: scribbles]
|
Backtracking
[solutions]
|
L13:
Dynamic programming:
splitting strings, longest increasing subsequence
[slides
:
scribbles]
|
Dynamic programming
[solutions]
|
|
Week 8: Oct 14-18
|
L14:
More DP: Edit Distance,
MIS in trees
memoization and edit
distance
[slides
: scribbles]
|
More dynamic programming
[solutions]
|
L15:
More dynamic programming,
CYK
Algorithm,
DP via DAGs,
DAGs, extraction order, and longest path
in linear
time
[CYK
: scribbles],
|
Yet even still more
dynamic programming
Drop deadline
[solutions]
|
|
Week 9: Oct 21-Oct 25
|
L16: Graphs, basic search,
Directed graphs, depth-first search
[slides
:
scribbles]
|
Graph modeling
[solutions]
|
L17:
DFS/Strong
connected components
[slides
:
scribbles]
[Graph notes]
|
Graph modeling
[solutions]
|
|
Week 10: Oct 28-Nov 1
|
L18:
BFS,
Shortest Paths, Dijkstra
[slides :
scribbles]
|
Shortest paths
[solutions]
|
L19:
Shortest Paths: Negative
Lengths via DP : All Pairs Shortest Path
[slides
:
scribbles]
|
More shortest paths
[solutions]
|
|
Week 11: Nov 4-Nov 8
|
ELECTIONS DAY
Vote early and vote often
L20:
Greedy algorithms
[slides]
|
Greedy
[solutions]
|
Review sessions for midterm
[scribbles] |
Fodder: Optional
review for Midterm 2
|
|
Week 12: Nov 11-Nov 19
|
| Midterm 2:
11/11/2024, Monday, 7pm-9:30pm
(details):
solution.
|
L21: MST Algorithms
[slides
: scribbles]
|
MST
[solutions]
|
L22: Unweighted Bipartite
Matchings
[slides
|
Matchings
[solutions]
|
|
Week 13: Nov 18-Nov 23
|
L23:
Polynomial time Reductions
[slides
: scribbles]
|
Self Reductions
[solutions]
|
L24: NP, NP-Completeness,
3SAT to Independent Set
[slides
:
scribbles]
[helpful video on P vs NP]
|
NP-hardness proofs
[solutions]
|
| Nov 23-Dec 1
|
Absolutely give thanks, go on vacation.
|
|
Week 14: Dec 2-Dec 6
|
More NP-hardness
reductions: 3-coloring, Hamiltonian cycle
[slides
: scribbles]
|
NP-Hardness, the final chapter
[solutions]
|
More more more NP
Completeness.
[slides
: scribbles]
|
Self redutions and NPC
[solutions]
|
|
Week 14: Dec 9-Dec 13
|
Wrap-up and preliminary review for the final exam
|
Review
for final
|
WRITING DAY |
|
|
Final exam
|