Course Calendar

Stars ★ indicate course material that has been updated or revised this semester. Links to future resources (videos, scribbles, labs, solutions, etc.) are placeholders. Future lecture and lab topics, lab handouts, and GPS/homework deadlines are subject to change. Exam dates are fixed.

Semester progress: Estimated time to completion: 17 minutes

MT1

MT2

Final

Week 1

Tue Aug 22: Lecture: Adminis trivia and course goals; strings and induction
[lecture scribbles, ~~no lecture video~~, makeup scribbles, makeup video]
Wed Aug 23: Lab 1a: String induction — [solutions] [induction notes] [helpful advice on writing proofs]
Thu Aug 24: Lecture: Languages and regular expressions — [scribbles, video]
Fri Aug 25: Lab 1b: Regular expressions — [solutions]
Mon Aug 28: Guided problem set 1 due at 9pm
Tue Aug 29: Homework 1 due at 9pm — [solutions]

Week 2

Tue Aug 29: Lecture: DFAs: intuition, definitions, examples — [scribbles, video]
Wed Aug 30: Lab 2a: DFAs — [solutions]
Thu Aug 31: Lecture: DFAs: product construction, closure, automatic=regular — [scribbles, video]
Fri Sep 1: Lab 2b: DFA product construction — [solutions]
Fri Sep 1: ⚠️ Registration deadline (11:59pm)
Mon Sep 4: Labor Day — GPS2 and HW2 due one day later than usual
Tue Sep 5: Guided problem set 2 due at 9pm
Wed Sep 6: Homework 2 due at 9pm — [solutions]

Week 3

Tue Sep 5: Lecture: Proving nonregularity via fooling sets; NFAs: intuition and examples — [scribbles, video, additional fooling set notes by Eric Huber]
Wed Sep 6: Lab 3a: Proving nonregularity — [solutions]
Thu Sep 7: Lecture: NFAs: ε-transitions, equivalence with DFAs — [scribbles, video]
Fri Sep 8: Lab 3b: Regular expression to NFA to DFA (to regular expression) — [solutions]
Mon Sep 11: Guided problem set 3 due at 9pm
Tue Sep 12: Homework 3 due at 9pm — [solutions]

Week 4

Tue Sep 12: Lecture: Language transformations — [scribbles, video]
Wed Sep 13: Lab 4a: Language transformations — [solutions]
Thu Sep 14: Lecture: Context-free languages and grammars — [scribbles, video]
Fri Sep 15: Lab 4b: Context-free grammars — [solutions]
Mon Sep 18: Guided problem set 4 due at 9pm
Tue Sep 19: Homework 4 due at 9pm — [solutions]

Week 5

Tue Sep 19: Lecture: Turing machines — [scribbles, video]
Wed Sep 20: Lab 5: More language transformations — [solutions]
Thu Sep 21: No lecture — Optional review for Midterm 1
[practice exam, answer booklet, solutions, redo solutions, video]
Fri Sep 22: No labs — Optional review for Midterm 1
Mon Sep 25: Midterm 1: 7–9pm — [solutions] — No guided problem set this week
Tue Sep 26: Conflict Midterm 1: 11am–1pm — [solutions] — No homework this week

Week 11

Tue 🎃ct 31: Lecture: Bellman-Ford again and Floyd-Warshall — [scribbles, video]
Wed Nov 1: Lab 11: Solve it both ways — [solutions]
Thu Nov 2: No lecture — Optional review for Midterm 2 — [practice exam, solutions, video]
Fri Nov 3: No lab — Optional review for Midterm 2
Mon Nov 6: Midterm 2: 7–9pm — [solutions] — No guided problem set this week
Tue Nov 7: Conflict Midterm 2: 11am–1pm — [solutions] — No homework this week

Week 12

Tue Nov 7: Lecture: Reductions: Cliques and friends, Hamiltonian cycles — [scribbles, video]
Wed Nov 8: Lab 12a: Reductions — [solutions]
Thu Nov 9: Lecture: P vs NP, NP-hardness, 3SAT, reduction to max independent set — [scribbles, video]
Fri Nov 10: Lab 12b: NP-hardness proofs — [solutions]
Mon Nov 13: Guided problem set 10 due at 9pm
Tue Nov 14: Homework 10 due at 9pm — [solutions]

Week 13

Tue Nov 14: Lecture: NP-hardness: Vertex cover to Hamiltonian cycle — [scribbles, video]
Wed Nov 15: Lab 13a: More NP-hardness proofs — [solutions]
Thu Nov 16: Lecture: NP-hardness: Why bother, Choosing which problem to reduce from [scribbles, video]
Fri Nov 17: Lab 13b: Even more NP-hardness proofs — [solutions]
Nov 18–26: Fall break — HW11 due one week later than usual
Mon Nov 27: ~~No guided problem set this week~~
Tue Nov 28: Homework 11 due at 9pm — [solutions]

Nov 18–26 — Inconveniently Scheduled Fall Break

Week 14

Sat Nov 25: ICES forms available
Tue Nov 28: Lecture: Undecidability: code is data, the halting problem — [scribbles, video]
Wed Nov 29: Lab 14a: Yet even still more NP-hardness practice — [solutions]
Thu Nov 30: Lecture: Undecidability: reductions and Rice's theorem — [scribbles, video]
Fri Dec 1: Lab 14b: Using Rice's Theorem — [solutions]
Never: Lab 14c: Undecidability Reductions (practice only) — [solutions]
Mon Dec 4: Guided problem set 11 due at 9pm
Homework 12 (practice only) "due" at 9pm — [solutions]

Week 15

Tue Dec 5: Lecture: Wrap-up and final exam review [practice exam 1, answer booklet, solutions, video part 1, video part 2]
Wed Dec 6: No labs — Optional review for the final exam
Thu Dec 7: Reading Day
ICES forms due (11:59pm)
TA feedback survey due (11:59pm)
CA feedback survey due (11:59pm)
Fri Dec 8: Final exam: 8–11am — [solutions]
Mon Dec 11: Conflict final exam: 8–11am
Tue Dec 12: Conflict final exam: 8–11am