1
Aug 22-26
|
Adminis+
trivia and course goals
Introduction and history;
strings
L1: [slides1,
slides2
: scribbles]
|
String induction
[induction notes,
more]
[solutions]
|
Languages and regular expressions
L2:
[slides
:
scribbles]
|
Regular expressions
[solutions]
|
2
Aug 29-Sep 2 |
DFAs, product construction
[Automata Tutor]
DFA Proofs
L3: [slides :
scribbles]
|
DFA construction
[solutions]
|
Non-determinism, NFAs
Jeff's NFA notes
L4: [slides]
|
DFA product construction
[solutions]
[ms : ct] |
3
Sep 5-9
|
NFAs continued, equivalence with DFAs and
regular expressions
Jeff's NFA notes
Converting NFA
to regex
L5:
[slides
:
scribbles]
|
DFA/NFA transformation
[solutions]
|
Proving non-regularity via fooling sets
[DFA Proofs]
[Fooling
sets guide]
L6:
[slides
:
scribbles
:
h]
|
Proving non-regularity
[solutions]
|
4
Sep 12-16
|
Context-free languages and grammars
L7:
[slides
: scribbles]
|
Context-free grammars
[h]
[solutions]
|
More on
Context-free languages and grammars
L7:
[slides
: scribbles]
|
Regular or not?
[h]
[solutions]
|
5
Sep 19-23
|
Turing
machines: history, formal definitions, examples,
variations
L8: [slides]
|
Algorithms for langs
[solutions]
|
Optional review for Midterm 1
|
Optional review
for Midterm 1
|
| Midterm 1: Monday, September 26, 7pm-9:30pm
(details):
solution.
|
6
Sep 26-30 |
Recursion: Hanoi,
mergesort
[slides
: scribbles]
[solving recurrences]
|
Hint: Binary search
[solutions]
|
Divide and conquer: linear-time selection,
Karatsuba multiplication
[recurrence notes]
[slides
: scribbles]
|
Divide and conquer
[solutions]
|
7
Oct 3-7 |
Backtracking:
independent set, longest increasing subsequence
[slides
: scribbles]
|
Backtracking
[solutions]
|
Dynamic programming:
splitting strings, longest increasing subsequence
[slides
:
scribbles]
|
Dynamic programming
[solutions]
|
8
Oct 10-14 |
More DP: Edit Distance,
MIS in trees
memoization and edit
distance
[slides
: scribbles]
|
More dynamic programming
[solutions]
|
More dynamic programming,
CYK
Algorithm
DP via DAGs
[CYK
: scribbles] ,
|
Yet even still more
dynamic programming
Drop deadline
[solutions]
|
9
Oct 17-21 |
Graphs, basic search,
Directed graphs, depth-first search
[slides
:
scribbles]
|
Graph modeling
[solutions]
|
DFS/Strong connected components
[slides
:
scribbles]
[Graph notes]
|
Graph modeling
[solutions]
|
10
Oct 24-28 |
DFS/Strong connected components
[slides
:
scribbles]
|
Shortest paths
[solutions]
|
BFS and
Shortest Paths
[slides :
scribbles]
|
More shortest paths
[solutions]
|
11
Oct 31 - Nov 4 |
Shortest Paths with Negative
Lengths via DP
[slides
: scribbles]
|
Greedy
[solutions]
|
Review sessions for midterm
[scribbles] |
Fodder: Optional
review for Midterm 2
|
| Midterm 2:
Monday, November 7, 7pm-9:30pm
(details):
solution.
|
12
Nov 7-11 |
ELECTION DAY (Nov 8)
Vote early and vote often
|
No discussion in lieu of midterm |
MST Algorithms
[slides
: scribbles]
|
MST
[solutions]
|
13
Nov 14-18
|
Polynomial time Reductions
[slides
: scribbles]
|
Self Reductions
[solutions]
|
NP, NP-Completeness,
3SAT to Independent Set
[slides
:
scribbles]
[helpful video on P vs NP]
|
NP-hardness proofs
[solutions]
|
| Nov 19-27
|
Definitely give thanks, go on vacation.
|
14
Nov 28-Dec 2 |
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]
|
15
Dec 5-9 |
Wrap-up and preliminary review for the final exam
|
Review
for final
|
READING DAY |
|
Final exam: Friday,
12/9/22 8-11
Conflict exam. See here.
|
|
Study material for the final
|