1
Aug 2226

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 29Sep 2 
DFAs, product construction
[Automata Tutor]
DFA Proofs
L3: [slides :
scribbles]

DFA construction
[solutions]

Nondeterminism, NFAs
Jeff's NFA notes
L4: [slides]

DFA product construction
[solutions]
[ms : ct] 
3
Sep 59

NFAs continued, equivalence with DFAs and
regular expressions
Jeff's NFA notes
Converting NFA
to regex
L5:
[slides
:
scribbles]

DFA/NFA transformation
[solutions]

Proving nonregularity via fooling sets
[DFA Proofs]
[Fooling
sets guide]
L6:
[slides
:
scribbles
:
h]

Proving nonregularity
[solutions]

4
Sep 1216

Contextfree languages and grammars
L7:
[slides
: scribbles]

Contextfree grammars
[h]
[solutions]

More on
Contextfree languages and grammars
L7:
[slides
: scribbles]

Regular or not?
[h]
[solutions]

5
Sep 1923

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, 7pm9:30pm
(details):
solution.

6
Sep 2630 
Recursion: Hanoi,
mergesort
[slides
: scribbles]
[solving recurrences]

Hint: Binary search
[solutions]

Divide and conquer: lineartime selection,
Karatsuba multiplication
[recurrence notes]
[slides
: scribbles]

Divide and conquer
[solutions]

7
Oct 37 
Backtracking:
independent set, longest increasing subsequence
[slides
: scribbles]

Backtracking
[solutions]

Dynamic programming:
splitting strings, longest increasing subsequence
[slides
:
scribbles]

Dynamic programming
[solutions]

8
Oct 1014 
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 1721 
Graphs, basic search,
Directed graphs, depthfirst search
[slides
:
scribbles]

Graph modeling
[solutions]

DFS/Strong connected components
[slides
:
scribbles]
[Graph notes]

Graph modeling
[solutions]

10
Oct 2428 
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, 7pm9:30pm
(details):
solution.

12
Nov 711 
ELECTION DAY (Nov 8)
Vote early and vote often

No discussion in lieu of midterm 
MST Algorithms
[slides
: scribbles]

MST
[solutions]

13
Nov 1418

Polynomial time Reductions
[slides
: scribbles]

Self Reductions
[solutions]

NP, NPCompleteness,
3SAT to Independent Set
[slides
:
scribbles]
[helpful video on P vs NP]

NPhardness proofs
[solutions]

Nov 1927

Definitely give thanks, go on vacation.

14
Nov 28Dec 2 
More NPhardness
reductions: 3coloring, Hamiltonian cycle
[slides
: scribbles]

NPHardness, the final chapter
[solutions]

More more more NP
Completeness.
[slides
: scribbles]

Self redutions and NPC
[solutions]

15
Dec 59 
Wrapup and preliminary review for the final exam

Review
for final

READING DAY 

Final exam: Friday,
12/9/22 811
Conflict exam. See here.

Study material for the final
