Course Calendar

Stars ★ indicate course material that has been updated or revised this semester. Future scribbes and solutions links are placeholders. Future lecture and lab topics, lab handouts, and GPS/homework deadlines are subject to change. Exam dates are fixed.

Semester progress:

MT1

MT2

Final

Jump to past weeks

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, location TBA — [solutions] — No guided problem set this week
Tue Sep 26: Conflict Midterm 1: time and location TBA — [solutions] — No homework this week

Week 11

Tue 🎃ct 31: Lecture: All-pairs shortest paths in detail — [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, location TBA — [solutions] — No guided problem set this week
Tue Nov 7: Conflict Midterm 2: time and location TBA — [solutions] — No homework this week

Week 12

Tue Nov 7: Lecture: Reductions, hardness — [scribbles, video]
Wed Nov 8: Lab 12a: Reductions — [solutions]
Thu Nov 9: Lecture: P vs NP, NP-hardness, NP-hardness reductions: 3SAT, Clique — [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: More NP-hardness: 3 Coloring, Hamiltonian cycle — [scribbles, video]
Wed Nov 15: Lab 13a: More NP-hardness proofs — [solutions]
Thu Nov 16: Lecture: Hamiltonian path, other NP hard problems, NP-hardness review [scribbles, video]
Fri Nov 17: Lab 13b: Even more NP-hardness proofs — [solutions]
Nov 18–26: Fall break — GPS11 and HW11 due one week later than usual
Mon Nov 27: Guided problem set 11 due at 9pm
Tue Nov 28: Homework 11 due at 9pm — [solutions]

Nov 18–26 — Inconveniently Scheduled Fall Break

Week 14

Mon Nov 27: 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 examples — [solutions]
Thu Nov 30: Lecture: Undecidability: reductions and Rice's theorem — [scribbles, video, skipped lab on undecidability reductions, skipped lab solutions]
Fri Dec 1: Lab 14b: Using Rice's Theorem — [solutions]
Mon Dec 4: Guided problem set 12 due at 9pm
Tue Dec 5: Homework 12 (practice only) "due" at 9pm — [solutions]

Week 15

Tue Dec 5: Lecture: Wrap-up and final exam review [scribbles, video]
Wed Dec 6: Final exam review
Wed Dec 6: ⚠️ ICES deadline (11:59pm)
Thu Dec 7: Reading Day
Fri Dec 8: Final exam: 8–11am, location TBA — [solutions]
TBA: Conflict final exam

Past Weeks

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]