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.
Week 6
- Tue Sep 29
- Lecture:
Recursion: Tower of Hanoi, mergesort, quicksort
— [scribbles; video; Erickson Algorithms 1] - Wed Sep 30
- Lab 6a: Try Binary searching — [solutions]
- Thu Oct 01
- Lecture:
Divide and conquer: linear-time selection, multiplication
— [scribbles; video; Erickson Algorithms 1] - Fri Oct 02
- Lab 6b: Fun with Karatsuba — [solutions]
- Mon Oct 05
- Guided problem set 5: Divide and conquer, recursion, and recurrences
- Tue Oct 06
- Homework 5: Divide and conquer
Week 7
- Tue Oct 06
- Lecture:
Backtracking: n queens, text segmentation, subset sum(?)
— [scribbles; video; 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
Week 8
- 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
Week 9
- 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
Week 10
- 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
Week 11
- 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)
Week 12
- 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
Week 13
- 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 Dec 01
- Homework 11: More NP-hardness
Week 14
- 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
- Guided problem set 11: Undecidability
- Mon Dec 07
Homework 12 (practice only) “due” by tomorrow
Week 15
- Tue Dec 08
- Lecture:
Wrap-up and review for Final Exam
- Wed Dec 09
No labs — Optional review for Final Exam
- Thu Dec 10
Reading Day — FLEX feedback due
- Fri Dec 11
- Final Exam: 8:00am-11:00am
Past weeks
Week 1
- Tue Aug 25
- Lecture:
Course goals and administrivia
;strings and induction
— [scribbles; video; Erickson Models 1; induction notes; helpful advice on writing proofs] - Wed Aug 26
- Lab 1a: String induction — [solutions; induction notes; helpful advice on writing proofs]
- Thu Aug 27
- Lecture:
Languages and regular expressions
— [scribbles; video; Erickson Models 2; helpful advice on writing proofs] - Fri Aug 28
- Lab 1b: Regular expressions — [solutions]
- Mon Aug 31
- Guided problem set 1: Prerequisite material, string induction, and regular expressions
- Tue Sep 01
- Homework 1: Strings and induction — [solutions]
Week 2
- Tue Sep 01
- Lecture:
DFAs: intuition, definitions, examples
— [scribbles; video; Erickson Models 3] - Wed Sep 02
- Lab 2a: DFA design — [solutions]
- Thu Sep 03
- Lecture:
DFAs: product construction, closure, automatic=regular
;NFAs: intuition and examples
— [scribbles; video; Erickson Models 3; Erickson Models 4] - Fri Sep 04
- Lab 2b: DFA product construction — [solutions]
- Fri Sep 04
⚠️ Registration deadline (11:59pm)
- Mon Sep 07
Labor Day — GPS2 and HW2 due one day later than usual and no homework party
— [Labor Day]- Tue Sep 08
- Guided problem set 2: Regular expressions and DFAs
- Wed Sep 09
- Homework 2: Regular expressions, DFAs — [solutions]
Week 3
- Tue Sep 08
- Lecture:
NFAs: ε-transitions, equivalence with DFAs and regular expressions
— [scribbles; video; Erickson Models 4] - Wed Sep 09
- Lab 3a: NFA design — [solutions]
- Thu Sep 10
- Lecture:
Proving nonregularity: fooling sets (and closure properties)
— [scribbles; video; Erickson Models 3] - Fri Sep 11
- Lab 3b: Proving nonregularity — [solutions]
- Mon Sep 14
- Guided problem set 3: DFAs, NFAs, and fooling sets
- Tue Sep 15
- Homework 3: Proving irregularity, regular or not? — [solutions]
Week 4
- Tue Sep 15
- Lecture:
Language transformations
— [scribbles; video; Erickson Models 4; extra language transformation notes by Pranay Midha] - Wed Sep 16
- Lab 4a: Language transformations — [solutions]
- Thu Sep 17
- Lecture:
Context-free grammars and languages
— [scribbles; video; Erickson Models 5] - Fri Sep 18
- Lab 4b: Context-free grammars — [solutions]
- Mon Sep 21
- Guided problem set 4: Language transformations and CFGs
- Tue Sep 22
- Homework 4: Language transformations, CFGs — [solutions]
Week 5
- Tue Sep 22
- Lecture:
Turing machines
— [scribbles; video; Erickson Models 6] - Wed Sep 23
- Lab 5: Language transformation and CFG practice — [solutions]
- Thu Sep 24
No lecture — Optional review for Midterm 1
— [practice 1; practice 1 answer booklet; practice 1 solutions; practice 1 video part i; practice 1 video part ii]- Fri Sep 25
No labs — Optional review for Midterm 1
— [practice 2; practice 2 answer booklet; practice 2 solutions; practice 2 video]- Sun Sep 27
Optional review party for Midterm 1 6pm–8pm in Siebel 0216
— [practice 3; practice 3 answer booklet; practice 3 solutions; practice 3 video]- Mon Sep 28
- Midterm 1: 7:00pm- 9:00pm — [solutions]
- Tue Sep 29
- Conflict Midterm 1: (time TBA) — [solutions]