1
Aug 28
- Sep 1 |
Adminis+trivia
and course goals
Introduction and history;
strings
L1: [slides1,
slides2]
|
String induction
[induction notes,
more]
[solutions]
|
Languages and regular
expressions
L2: [slides]
|
Regular expressions
[solutions]
|
2
Sep 4-8 |
DFAs, product construction
[Automata Tutor]
DFA Proofs
L3: [slides]
|
DFA construction
[solutions]
|
Non-determinism, NFAs
Jeff's NFA notes
L4: [slides]
|
DFA product construction
[solutions]
|
3
Sep 11-15 |
NFAs continued, equivalence with DFAs and regular
expressions
Jeff's NFA notes
Converting NFA to regex
L5: [slides]
|
DFA/NFA transformation
[solutions]
|
Proving non-regularity via fooling sets
[DFA Proofs]
[Fooling sets guide]
L6: [slides]
|
Proving nonregularity
[solutions]
|
4
Sep 18-22 |
Context-free languages and grammars
L7: [slides]
|
Context-free grammars
[solutions]
|
Turing machines: history, formal definitions,
examples, variations
L8: [slides]
|
Regular or not?
[solutions]
|
5
Sep 25-29 |
Halting and undecidability
[NO SLIDES]
|
Turing machine design
[solutions]
|
Optional review for Midterm 1
|
Optional review for Midterm 1
|
| Skillset for midterm
1
|
Midterm 1: Monday, October 2, 7-9pm
Conflict exam: TBD TBD |
6
Oct 2-6 |
Recursion: Hanoi, mergesort
[slides][solving recurrences]
|
Hint: Binary search
[solutions]
|
Divide and conquer: linear-time selection,
Karatsuba multiplication
[recurrence notes]
[slides]
|
Divide and conquer
[solutions]
|
7
Oct 9-13 |
Backtracking: independent set, longest
increasing subsequence
[slides]
|
Backtracking
[solutions]
|
Dynamic programming: splitting strings,
longest increasing subsequence
[slides]
|
Dynamic programming
[solutions]
|
8
Oct 16-20 |
More DP: Edit Distance, MIS in trees
memoization and edit distance
[slides]
|
More dynamic programming
[solutions]
|
CYK Algorithm,
Graphs, basic search
[CYK, Graph search slides]
|
Yet even still more dynamic programming
Drop deadline
[solutions]
|
9
Oct 23-27 |
Directed graphs, depth-first search
|
Graph modeling
[solutions]
|
DFS/Strong connected compoments
[slides]
[Graph notes]
|
Graph modeling
[solutions]
|
10
Oct 30- Nov 3 |
BFS and Shortest Paths
[slides]
|
Shortest paths
[solutions]
|
Shortest Paths with Negative Lengths via DP
[slides]
|
More shortest paths
[solutions]
|
11
Nov 6-10 |
Greedy algorithms
[slides]
|
Greedy
[solutions]
|
MST Algorithms
[slides]
|
Optional review for Midterm 2
|
| Skillset for midterm
2
|
Midterm 2: Monday, November 13, 7-9pm
Where + cover page
Conflict exam: Wednesday, November 15, 7-9pm, in
SC 1131
|
12
Nov 13-17 |
No lecture in lieu of midterm |
MST
[solutions]
|
Undecidability: halting problem, diagonalization, reductions
[slides]
|
Undecidability via reductions
[solutions]
|
| Nov 18-26 |
Give thanks, go on vacation. |
13
Nov 27
- Dec 1 |
Polynomial time Reductions
[slides]
|
Self Reductions
[solutions]
|
NP, NP-Completeness,
3SAT to Independent Set
[Slides]
[helpful video on P vs NP]
|
NP-hardness proofs
[solutions] |
14
Dec 4-8 |
More NP-hardness reductions: 3-coloring, Hamiltonian cycle
[Slides]
|
NP-Hardness, the final chapter
[solutions]
|
More more more NP Completeness.
[slides]
ICES Forms
|
Using Rice's Theorem
ICES Forms
[solutions]
|
15
Dec 11-15 |
Wrap-up and preliminary review for the final exam |
Review for final
|
Reading Day |
|
| Skill
set for final
|
Final exam:
Monday, December 18 8:00-11:00 a.m.
Conflict final: Tuesday, December 19, 10:00-13:00
SC 0216 |