1
Jan 20-24
|
Administrivia
and course goals
Introduction and history;
strings
L1: [scribbles]
|
String induction
[more]
[solutions]
|
Languages and regular
expressions
L2: [slides] [annotated slides]
|
Regular expressions
[solutions]
|
2
Jan 27-31 |
DFAs
L3: [slides] [annotated slides]
|
DFA construction
[solutions]
|
DFA product construction
L4: [slides] [annotated slides]
|
DFA product construction
[solutions]
|
3
Feb 3-7 |
Non-determinism, NFAs
L5: [slides] [annotated slides]
|
NFAs
[solutions]
|
NFAs continued, equivalence with DFAs and regular
expressions
Converting NFA to regex (Sariel's notes)
L6: [slides] [annotated slides]
[scribbles]
|
Regular language transformation
[solutions]
|
4
Feb 10-14 |
Proving non-regularity via fooling sets
L7: [slides] [annotated slides]
|
Proving non-regularity
[solutions]
|
Context-free languages and grammars
L8: [slides] [annotated slides]
|
Context-free grammars
[solutions]
|
5
Feb 17-21 |
Turing machines: history, formal definitions,
examples, variations
L9: [slides]
|
Turing machine design
[solutions]
|
Optional review for Midterm 1
[scribbles]
|
Optional review for Midterm 1
|
Midterm 1: Feb 24 Monday 7-9pm, at Foellinger Auditorium
(cover page :
skillset)
Conflict: Feb 26 Wednesday 7-9pm, at DCL 1310
|
6
Feb 24-28 |
Recursion: Hanoi, mergesort
[slides] [annotated slides]
[solving recurrences] [Big-O Notation]
|
Hint: Binary search
[solutions]
|
Divide and conquer: linear-time selection,
Karatsuba multiplication
[slides] [annotated slides]
[recurrence notes] [Big-O Notation]
|
Divide and conquer
[solutions]
|
7
Mar 2-6 |
Backtracking: independent set, longest
increasing subsequence
[slides] [annotated slides]
|
Backtracking
[solutions]
|
Dynamic programming: splitting strings,
longest increasing subsequence
[slides] [annotated slides]
|
Dynamic programming
[solutions]
|
8
Mar 9-13 |
More DP: LIS, Edit Distance
[slides]
[annotated slides on LIS] [annotated slides on Edit distance]
|
More dynamic programming
[solutions]
|
More DP: Edit Distance, MIS in trees
memoization and edit distance
[slides]
[annotated slides]
|
Yet even still more dynamic programming
[solutions]
Old drop deadline.
|
| Mar 14-22 |
Spring break. |
9
Mar 23-27 |
Graphs, basic search
[slides], [annotated slides]
|
Graph modeling
[solutions]
|
DFS/Strong connected compoments
[slides]
[annotated slides]
|
Graph modeling
[solutions]
|
10
Mar 30-
Apr 3 |
BFS and Shortest Paths
[slides]
[annotated slides]
|
Shortest paths
[solutions]
|
Shortest Paths with Negative Lengths via DP All-Pair-Shortest-Path via DP
[slides]
[annotated slides]
|
More shortest paths
[solutions]
|
11
Apr 6-10 |
Greedy algorithms
[slides]
[scribbles]
|
Greedy
[solutions]
|
Optional review for Midterm 2
[scribbles]
|
Optional review for Midterm 2
|
Midterm 2: Apr 13 Monday 7pm-10pm Central Time
(skillset)
Conflict: Apr 14 Tuesday 7am-10am Central Time
|
|---|
12
Apr 13-17 |
MST Algorithms
[slides]
[scribbles]
|
MST
[solutions]
|
Undecidability: halting problem, diagonalization, reductions
[slides]
[scribbles]
|
Undecidability via reductions
[solutions]
|
13
Apr 20-24 |
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]
|
14
Apr 27
- May 1 |
More NP-hardness reductions: 3-coloring, Hamiltonian cycle
[slides]
[scribbles]
|
More NP-hardness
[solutions]
|
More more more NP Completeness.
[slides]
[scribbles]
|
NP-hardness: The final chapter
[(revised) solutions]
|
15
May 4-8 |
Wrap-up and preliminary review for the final exam
Scribbles:
[Undecidability]
[NPC]
|
Review for final
New new drop deadline (5/6).
|
Reading Day |
|
Final exam: May 8 Friday 7pm-11pm Central Time
(skillset)
Conflict final: TBA
|