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 and GPS/homework deadlines are subject to change. Exam dates are fixed.

Semester progress: 9/15 weeks done

MT1

MT2

Final

Jump to past weeks

Week 10

Tue Oct 28: Lecture: Dag DP; generic shortest paths, DagSSSP, BFS — [scribbles, video]
Wed Oct 29: Lab 10a: Topological sort — [solutions]
Thu Oct 30: Lecture: Shortest paths via Dijkstra and Bellman-Ford — [scribbles, video]
Fri 🎃ct 31: Lab 10b: Shortest paths — [solutions]
Mon Nov 3: Guided problem set 9 due at 9pm
Tue Nov 4: Homework 9 due at 9pm — [solutions]

Week 11

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

Week 12

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

Week 13

Tue Nov 18: Lecture: NP-hardness: Vertex cover to Hamiltonian cycle — [scribbles, video]
Wed Nov 19: Lab 13a: More NP-hardness proofs — [solutions]
Thu Nov 20: Lecture: NP-hardness: Why bother, choosing which problem to reduce from [scribbles, video]
Fri Nov 21: Lab 13b: Even more NP-hardness proofs — [solutions]
Nov 22–30: Fall break — HW11 due one week later than usual
Mon Dec 1: ~~No guided problem set this week~~
Tue Dec 2: Homework 11 due at 9pm — [solutions]

Nov 22–30 — Inconveniently Scheduled Fall Break 🦃

Week 14

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

Week 15

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

Past weeks

Week 1

Tue Aug 26: Lecture: Adminis trivia and course goals; strings and induction
[scribbles, video, Emily's scribbles, Emily's video]
Wed Aug 27: Lab 1a: String induction — [solutions] [induction notes] [helpful advice on writing proofs]
Thu Aug 28: Lecture: Languages and regular expressions — [scribbles, video]
Fri Aug 29: Lab 1b: Regular expressions — [solutions]
Mon Sep 1: Labor Day — GPS1 and HW1 due one day later than usual
Tue Sep 2: Guided problem set 1 due at 9pm
Wed Sep 3: Homework 1 due at 9pm — [solutions]

Week 2

Tue Sep 2: Lecture: ★ DFAs: intuition, definitions, examples — [scribbles, video]
Wed Sep 3: Lab 2a: DFAs — [solutions]
Thu Sep 4: Lecture: ★ DFAs: product construction, closure, automatic=regular — [scribbles, video]
Fri Sep 5: Lab 2b: DFA product construction — [solutions]
Fri Sep 5: ⚠️ Registration deadline (11:59pm)
Tue Sep 9: Guided problem set 2 due at 9pm
Wed Sep 10: Homework 2 due at 9pm — [solutions]

Week 3

Tue Sep 9: Lecture: ★ Proving nonregularity via fooling sets; ★NFAs: intuition and examples — [scribbles, video, additional fooling set notes by Eric Huber]
Wed Sep 10: Lab 3a: Proving nonregularity — [solutions]
Thu Sep 11: Lecture: ★ NFAs: ε-transitions, equivalence with DFAs and regular expressions — [scribbles, video]
Fri Sep 12: ★ Lab 3b: NFA design — [solutions]
Mon Sep 15: Guided problem set 3 due at 9pm
Tue Sep 16: Homework 3 due at 9pm — [solutions]

Week 4

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

Week 5

Tue Sep 23: Lecture: Turing machines — [scribbles, video]
Wed Sep 24: ★ Lab 5: More language transformations — [solutions]
Thu Sep 25: No lecture — Optional review for Midterm 1
[practice exam, answer booklet, solutions, video]
Fri Sep 26: No labs — Optional review for Midterm 1
[Practice exam 2: questions, answer booklet, solutions, video]
[Practice exam 3: questions, answer booklet, solutions, video]
Mon Sep 29: Midterm 1: 7–9pm — [solutions] — No guided problem set this week
Tue Sep 30: Conflict Midterm 1: [time TBA] — [solutions] — No homework this week