CS 374 A

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

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]

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 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: selection, multiplication [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: dag DP, strong components; generic shortest paths, BFS, DFS, and Dijkstra [scribbles, video]
Wed Oct 25
Lab 10a: Shortest paths [solutions]
Thu Oct 26
Lecture: Shortest paths via Dijkstra and Bellman-Ford [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: 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]
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