Course Calendar

Future lecture and lab topics and guided problem set/homework deadlines are subject to change.

All guided problem sets and written homeworks are due by 9pm unless announced otherwise.

Exam dates are fixed.

Semester progress: 0 / 15 weeks complete

MT1

MT2

Final

Week 1

Tue Aug 25: Lecture: Course goals and administrivia; strings and induction — [Erickson Models 1; induction notes; helpful advice on writing proofs]
Wed Aug 26: Lab 1a: String induction — [induction notes; helpful advice on writing proofs]
Thu Aug 27: Lecture: Languages and regular expressions — [Erickson Models 2; helpful advice on writing proofs]
Fri Aug 28: Lab 1b: Regular expressions
Mon Aug 31: Guided problem set 1: Prerequisite material, string induction, and regular expressions
Tue Sep 01: Homework 1: Strings and induction

Tue Sep 01: Lecture: DFAs: intuition, definitions, examples — [Erickson Models 3]
Wed Sep 02: Lab 2a: DFA design
Thu Sep 03: Lecture: DFAs: product construction, closure, automatic=regular — [Erickson Models 3]
Fri Sep 04: Lab 2b: DFA product construction
Fri Sep 04: ⚠️ Registration deadline (11:59pm)
Mon Sep 07: Labor Day — GPS1 and HW1 due one day later than usual
— [Labor Day]
Tue Sep 08: Guided problem set 2: Regular expressions and DFAs
Wed Sep 09: Homework 2: Strings and induction

Tue Sep 08: Lecture: Proving nonregularity: fooling sets (and closure properties); NFAs: intuition and examples — [Erickson Models 3; Erickson Models 4]
Wed Sep 09: Lab 3a: Proving nonregularity
Thu Sep 10: Lecture: NFAs: ε-transitions, equivalence with DFAs and regular expressions — [Erickson Models 4]
Fri Sep 11: Lab 3b: NFA design
Mon Sep 14: Guided problem set 3: DFAs and NFAs
Tue Sep 15: Homework 3: Proving irregularity, regular or not?

Tue Sep 15: Lecture: Language transformations — [Erickson Models 4; extra language transformation notes by Pranay Midha]
Wed Sep 16: Lab 4a: Language transformations
Thu Sep 17: Lecture: Context-free grammars and languages — [Erickson Models 5]
Fri Sep 18: Lab 4b: Context-free grammars
Mon Sep 21: Guided problem set 4: Fooling sets, language transformations, and CFGs
Tue Sep 22: Homework 4: Language transformations, CFGs

Tue Sep 29: Lecture: Recursion: Tower of Hanoi, mergesort, and quicksort — [Erickson Algorithms 1]
Wed Sep 30: Lab 6a: Try Binary searching
Thu Oct 01: Lab 6b: Fun with Karatsuba
Thu Oct 01: Lecture: Divide and conquer: linear-time selection, multiplication — [Erickson Algorithms 1]
Mon Oct 05: Guided problem set 5: Divide and conquer, recursion, and recurrences
Tue Oct 06: Homework 5: Divide and conquer

Tue Oct 06: Lecture: Backtracking: $n$ queens, text segmentation, subset sum(?) — [Erickson Algorithms 2]
Wed Oct 07: Lab 7a: Backtracking
Thu Oct 08: Lecture: Dynamic programming: Fibonacci numbers, faster text segmentation — [Erickson Algorithms 3]
Fri Oct 09: Lab 7b: Dynamic programming
Mon Oct 12: Guided problem set 6: Dynamic programming
Tue Oct 13: Homework 6: Dynamic programming

Tue Oct 13: Lecture: Dynamic programming with sequences: Edit distance — [Erickson Algorithms 3]
Wed Oct 14: Lab 8a: More dynamic programming
Thu Oct 15: Lecture: Tree shaped dynamic programming: woodcutting, maximum independent set in trees — [Erickson Algorithms 3]
Fri Oct 16: Lab 8b: Dynamic Programming: Return of the King
Fri Oct 16: ⚠️ Drop deadline (11:59pm)
Mon Oct 19: Guided problem set 7: More dynamic programming
Tue Oct 20: Homework 7: More dynamic programming

Tue Oct 20: Lecture: Graphs: definitions, representations, traversal, reductions, layering — [Erickson Algorithms 5]
Wed Oct 21: Lab 9a: Applying graph traversals
Thu Oct 22: Lecture: Depth-first search, topological sort, dynamic programming on dags — [Erickson Algorithms 6]
Fri Oct 23: Lab 9b: Applying DAGs
Mon Oct 26: Guided problem set 8: Graph algorithms
Tue Oct 27: Homework 8: Graph algorithms

Tue Oct 27: Lecture: Single-source shortest paths: generic single-source shortest paths, breadth-first search, Dijkstra's algorithm — [Erickson Algorithms 8]
Wed Oct 28: Lab 10a: Applying shortest paths
Thu Oct 29: Lecture: Single-source shortest paths via dags: DagSSSP, Bellman-Ford (kind of) via layering — [Erickson Algorithms 8]
Fri Oct 30: Lab 10b: More applying shortest paths
Mon Nov 02: Guided problem set 9: More graph algorithms
Tue Nov 03: Homework 9: More graph algorithms

Tue Nov 03: Lecture: Shortest paths via direct dynamic programming: Bellman-Ford for real this time, Floyd-Warshall all-pairs shortest paths — [Erickson Algorithms 8; Erickson Algorithms 9]
Wed Nov 04: Lab 11: Solve it both ways
Thu Nov 05: No lecture — Optional review for Midterm 2
Fri Nov 06: No labs — Optional review for Midterm 2
Mon Nov 09: Midterm 2: 7:00pm- 9:00pm
Tue Nov 10: Conflict Midterm 2: (time TBA)

Tue Nov 10: Lecture: Polynomial time (Karp) reductions: definitions, IndependentSet and friends — [Erickson Algorithms 12]
Wed Nov 11: Lab 12a: Polynomial time reductions
Thu Nov 12: Lecture: NP-hardness: definitions, SAT, 3SAT — [Erickson Algorithms 12]
Fri Nov 13: Lab 12b: NP-hardness proofs
Mon Nov 16: Guided problem set 10: Polynomial time reductions and NP-hardness
Tue Nov 17: Homework 10: NP-hardness

Tue Nov 17: Lecture: NP-hardness proofs: 3SAT to IndependentSet, 3SAT to HamCycle, VertexCover to SubsetSum — [Erickson Algorithms 12]
Wed Nov 18: Lab 13a: More NP-hardness proofs
Thu Nov 19: Lecture: NP-hardness proofs: spill from earlier, why bother, choosing which problem to reduce from — [Erickson Algorithms 12]
Fri Nov 20: Lab 13b: The NP-hardness Proofs Revolutions
Mon Nov 23: No guided problem set this week
Tue Nov 24: Fall Break — HW11 due one week later than usual
Tue Nov 24: Fall Break — HW11 due one week later than usual
Wed Dec 02: Homework 11: More NP-hardness

Nov 21-29 — Inconveniently Timed Fall Break 🦃

Tue Dec 01: Lecture: Undecidability: review of (Turing) machines, SelfReject, Halt — [Erickson Models 7]
Wed Dec 02: Lab 14a: Undecidability via diagonalization
Thu Dec 03: Lecture: Undecidability: reductions, Rice's theorem — [Erickson Models 7]
Fri Dec 04: Lab 14b: Undecidability via reductions and Rice's theorem
Mon Dec 07: Homework 12 (practice only) “due” by tomorrow
Mon Dec 07: Guided problem set 11: Undecidability