1
Aug 24-28 |
Adminis+ trivia and course goals
Introduction and history; strings
L1: [slides1, slides2]
Scribbles |
String induction
[induction notes, more] [solutions]
[pre-recording] |
Languages and regular expressions
L2: [slides]
Scribbles |
Regular expressions
[solutions] |
2
Aug 31-Sep 4 |
DFAs, product construction
[Automata Tutor] DFA Proofs
L3: [slides]
Scribbles |
DFA construction
[solutions]
[prerecorded] |
Non-determinism, NFAs
Jeff's NFA notes
L4: [slides]
Scribbles |
DFA product construction
[solutions]
[yt : ms : ct] |
3
Sep 7-11 |
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 |
Proving non-regularity
[solutions] |
4
Sep 14-18 |
Context-free languages and grammars
L7: [slides]
Scribbles |
Context-free grammars
[solutions] |
Turing machines: history, formal definitions, examples, variations
L8: [slides]
Scribbles |
Regular or not?
[solutions] |
5
Sep 21-25 |
Halting and undecidability
L9: [slides]
Scribbles |
Undecidability
[solutions] |
Optional review for Midterm 1
Scribbles |
Optional review for Midterm 1 |
| Midterm 1: Sunday/Monday, September 27/28 (details): solution. |
6
Sep 28-Oct 2 |
Recursion: Hanoi, mergesort
[slides][solving recurrences]
Scribbles |
Hint: Binary search
[solutions] |
Divide and conquer: linear-time selection, Karatsuba multiplication
[recurrence notes] [slides]
Scribbles |
Divide and conquer
[solutions] |
7
Oct 5-9 |
Backtracking: independent set, longest increasing subsequence
[slides]
Scribbles
n queens demo(ipynb)(html) |
Backtracking
[solutions] |
Dynamic programming: splitting strings, longest increasing subsequence
[slides]
Scribbles
python memoize demo(ipynb) (html) |
Dynamic programming
[solutions] |
8
Oct 12-16 |
More DP: Edit Distance, MIS in trees
memoization and edit distance
[slides]
Scribbles |
More dynamic programming
[solutions] |
CYK Algorithm, Graphs, basic search
[CYK, Graph search slides]
Scribbles
optimal bst (ipynb) (html) |
Yet even still more dynamic programming
Drop deadline
[solutions] |
9
Oct 19-23 |
Directed graphs, depth-first search
Scribbles |
Graph modeling
[solutions] |
DFS/Strong connected components
[slides]
[Graph notes]
Scribble[1, 2] |
Graph modeling
[solutions] |
10
Oct 26-30 |
BFS and Shortest Paths
[slides]
Scribbles |
Shortest paths
[solutions] |
Shortest Paths with Negative Lengths via DP
[slides]
Scribble[1, 2] - Animation |
More shortest paths
[solutions] |
11
Nov 2-6 |
ELECTION DAY
Vote early and vote often |
Greedy
[solutions] |
Greedy algorithms
[slides]
Scribbles |
Fodder: Optional review for Midterm 2 |
| Midterm 2: Sunday/Monday, November 8/9 (details): solution. |
12
Nov 9-13 |
No lecture in lieu of midterm |
No discussion in lieu of midterm |
MST Algorithms [slides]
Scribbles |
MST
[solutions] |
13
Nov 16-20 |
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 21-29 |
Definitely give thanks, go on vacation. |
14
Nov 30-Dec 4 |
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 7-9 |
Wrap-up and preliminary review for the final exam
Scribbles |
Review for final |
|
|
| Dec 10 |
Reading day (Thursday) |
| Final exam time window: Dec 17, 12:01am - Dec 18, 11:59pm (CST). |
OLD Skill set for final
Study material for the final |