CS 374 A, Fall 2025
About this course Course staff Announcements Stuff you already know
Guided problem sets Lab handouts and solutions Homeworks and solutions Exams and solutions
Course calendar (with lecture notes and videos) Weekly events (including office hours)
PrairieLearn Gradescope (entry code R5B7GB) MediaSpace Ed Discussion Discord Other useful resources
Homework policies Exam policies Grading policies Accommodations Health and wellness Academic integrity Conduct

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: We're all done!!
MT1
MT2
Final

Week 1

Tue Aug 26
Lecture: Administrivia 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

Week 6

Tue Sep 30
Lecture: Recursion: Hanoi, mergesort, quicksort — [scribbles, video]
Wed Oct 1
Lab 6a: Hint: Binary search — [solutions]
Thu Oct 2
Lecture: Divide and conquer: selection, multiplication — [scribbles, video]
Fri Oct 3
Lab 6b: Fun with Karatsuba — [solutions]
Mon Oct 6
Guided problem set 5 due at 9pm
Tue Oct 7
Homework 5 due at 9pm — [solutions]

Week 7

Tue Oct 7
Lecture: Backtracking: n queens, game trees, text segmentation — [scribbles, video]
Wed Oct 8
Lab 7a: Backtracking — [solutions]
Thu Oct 9
Lecture: Dynamic programming: Fibonacci, text segmentation again — [scribbles, video]
Fri Oct 10
Lab 7b: Dynamic programming — [alternative version with many recurrences, solutions, alt solutions]
Mon Oct 13
Guided problem set 6 due at 9pm
Tue Oct 14
Homework 6 due at 9pm — [solutions]

Week 8

Tue Oct 14
Lecture: Sequence dynamic programming: edit distance — [scribbles, video]
Wed Oct 15
Lab 8: More dynamic programming — [solutions]
Thu Oct 16
Lecture: Tree-shaped dynamic programming: woodcutting, maximum independent set in trees —  [scribbles, video]
Fri Oct 17
Lab 8b: Return of the son of revenge of dynamic programming — [solutions]
Fri Oct 17
⚠️ Drop deadline (11:59pm)
Mon Oct 20
Guided problem set 7 due at 9pm
Tue Oct 21
Homework 7 due at 9pm — [solutions]

Week 9

Tue Oct 21
Lecture: Graphs: definitions, representations, data structures, traversal, reductions, flood fill — [scribbles, video]
Wed Oct 22
Lab 9a: Graph modeling — [graph layring notes, solutions]
Thu Oct 23
Lecture: Graph layering, WFS variants, depth-first search, topological sort — [scribbles, video]
Fri Oct 24
Lab 9b: More graph modeling — [graph layring notes, solutions]
Mon Oct 27
Guided problem set 8 due at 9pm
Tue Oct 28
Homework 8 due at 9pm — [solutions]

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 via layering and all-pairs shortest paths [jumbled Floyd-Warshall notes, scribbles, video]
Wed Nov 5
Lab 11: Solve it both ways — [solutions]
Thu Nov 6
No lecture — Optional review for Midterm 2
[practice exam, answer booklet, solutions, video]
Fri Nov 7
No lab — Optional review for Midterm 2
[Practice exam 2: questions, answer booklet, solutions, video]
[Practice exam 3: questions, answer booklet, solutions, video]
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]
Tue Nov 18
Homework 10 due at 9pm — [solutions]
Wed Nov 19
Guided problem set 10 due at 9pm

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 still more NP-hardness proofs — [solutions]
Lab 13c: Even more NP-hardness proofs (practice only) — [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]
Homework 11 due at 9pm — [solutions]
Wed Dec 3
Lab 14a: Beyond the Revenge of the Son of Planet of NP-hardness Practice, the Final Chapter, Part II: Electric Bugaloo (A Star Wars Story) — [solutions]
Thu Dec 4
Lecture: Undecidability: reductions and Rice's theorem — [scribbles; video; scribbles, take 2; video, take 2]
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

Sun Dec 7
No homework party — Optional review for the final exam
[Practice exam 1: questions, answer booklet, solutions, video]
Tue Dec 9
Lecture: Wrap-up and final exam review
[Practice exam 2: questions, answer booklet, solutions, video part i, video part ii]
Wed Dec 10
No labs — Optional review for the final exam
[Practice exam 3: questions, answer booklet, solutions, video]
Thu Dec 11
Reading Day — FLEX feedback due
Fri Dec 12
Final exam: 8–11am — [solutions]
Mon Dec 15
Conflict final exam: 8-11am — [solutions]