1
Jan 2024

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 2731 
DFAs
L3: [slides] [annotated slides]

DFA construction
[solutions]

DFA product construction
L4: [slides] [annotated slides]

DFA product construction
[solutions]

3
Feb 37 
Nondeterminism, 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 1014 
Proving nonregularity via fooling sets
L7: [slides] [annotated slides]

Proving nonregularity
[solutions]

Contextfree languages and grammars
L8: [slides] [annotated slides]

Contextfree grammars
[solutions]

5
Feb 1721 
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 79pm, at Foellinger Auditorium
(cover page :
skillset)
Conflict: Feb 26 Wednesday 79pm, at DCL 1310

6
Feb 2428 
Recursion: Hanoi, mergesort
[slides] [annotated slides]
[solving recurrences] [BigO Notation]

Hint: Binary search
[solutions]

Divide and conquer: lineartime selection,
Karatsuba multiplication
[slides] [annotated slides]
[recurrence notes] [BigO Notation]

Divide and conquer
[solutions]

7
Mar 26 
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 913 
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 1422 
Spring break. 
9
Mar 2327 
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 AllPairShortestPath via DP
[slides]
[annotated slides]

More shortest paths
[solutions]

11
Apr 610 
Greedy algorithms
[slides]
[scribbles]

Greedy
[solutions]

Optional review for Midterm 2
[scribbles]

Optional review for Midterm 2

Midterm 2: Apr 13 Monday 7pm10pm Central Time
(skillset)
Conflict: Apr 14 Tuesday 7am10am Central Time

12 Apr 1317 
MST Algorithms
[slides]
[scribbles]

MST
[solutions]

Undecidability: halting problem, diagonalization, reductions
[slides]
[scribbles]

Undecidability via reductions
[solutions]

13
Apr 2024 
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]

14
Apr 27  May 1 
More NPhardness reductions: 3coloring, Hamiltonian cycle
[slides]
[scribbles]

More NPhardness
[solutions]

More more more NP Completeness.
[slides]
[scribbles]

NPhardness: The final chapter
[(revised) solutions]

15
May 48 
Wrapup 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 7pm11pm Central Time
(skillset)
Conflict final: TBA
