CS 374 A

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:

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 6

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

Week 7

Tue Oct 3
Lecture: Backtracking: n queens, game trees, text segmentation [scribbles, video]
Wed Oct 4
Lab 7a: Backtracking [solutions]
Thu Oct 5
Lecture: Dynamic programming: Fibonacci, text segmentation again [scribbles, video]
Fri Oct 6
Lab 7b: Dynamic programming [solutions]
Mon Oct 9
Guided problem set 6 due at 9pm
Tue Oct 10
Homework 6 due at 9pm — [solutions]

Week 8

Tue Oct 10
Lecture: Sequence dynamic programming: Edit distance [scribbles, video]
Wed Oct 11
Lab 8: More dynamic programming [solutions]
Thu Oct 12
Lecture: Tree-shaped dynamic programming: Carpentry —  [scribbles, video]
Fri Oct 13
Lab 8b: Return of the son of revenge of dynamic programming [solutions]
Fri Oct 13
⚠️ Drop deadline (11:59pm)
Mon Oct 16
Guided problem set 7 due at 9pm
Tue Oct 17
Homework 7 due at 9pm — [solutions]

Week 9

Tue Oct 17
Lecture: Graphs: definitions, representations, data structures, traversal [scribbles, video]
Wed Oct 18
Lab 9a: Graph modeling [solutions]
Thu Oct 19
Lecture: Depth-first search, topological sort [scribbles, video]
Fri Oct 20
Lab 9b: Topological sort [solutions]
Mon Oct 23
Guided problem set 8 due at 9pm
Tue Oct 24
Homework 8 due at 9pm — [solutions]

Week 10

Tue Oct 24
Lecture: Dynamic programming in DAGs, strong components; generic shortest paths [scribbles, video]
Wed Oct 25
Lab 10a: Shortest paths [solutions]
Thu Oct 26
Lecture: Shortest paths via BFS, DFS, Disjktra, Bellman-Ford, and (briefly) Floyd-Warshall [scribbles, video]
Fri Oct 27
Lab 10b: All-pairs shortest paths [solutions]
Mon Oct 30
Guided problem set 9 due at 9pm
Tue 🎃ct 31
Homework 9 due at 9pm — [solutions]

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]
Conflict final exam

Past Weeks

Week 1

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