CS 374 A - Course Calendar

Week 2

Tue Jan 27: Lecture: DFAs: intuition, definitions, examples — [scribbles, video]
Wed Jan 28: Lab 2a: DFAs — [solutions]
Thu Jan 29: Lecture: DFAs: product construction, closure, automatic=regular — [scribbles, video]
Fri Jan 30: Lab 2b: DFA product construction — [solutions]
Mon Feb 02: Guided problem set 2 due at 9pm
Tue Feb 03: Homework 2 due at 9pm — [solutions]

Mon Feb 02: ⚠️ Registration deadline (11:59pm)
Tue Feb 03: Lecture: Proving nonregularity via fooling sets; NFAs: intuition and examples — [scribbles]
Wed Feb 04: Lab 3a: Proving nonregularity — [solutions]
Thu Feb 05: Lecture: NFAs: ε-transitions, equivalence with DFAs and regular expressions — [scribbles]
Fri Feb 06: Lab 3b: NFA design — [solutions]
Mon Feb 09: Guided problem set 3 due at 9pm
Tue Feb 10: Homework 3 due at 9pm — [solutions]

Tue Feb 24: Lecture: Recursion: Hanoi, mergesort — [scribbles]
Wed Feb 25: Lab 6a: Hint: Binary search — [solutions]
Thu Feb 26: Lecture: Divide and conquer: linear-time selection, multiplication — [scribbles]
Fri Feb 27: Lab 6b: Fun with Karatsuba — [solutions]
Mon Mar 02: Guided problem set 5 due at 9pm
Tue Mar 03: Homework 5 due at 9pm — [solutions]

Tue Mar 03: Lecture: Backtracking: independent set, longest increasing subsequence — [scribbles]
Wed Mar 04: Lab 7a: Backtracking — [solutions]
Thu Mar 05: Lecture: Dynamic programming: splitting strings, longest common subsequence — [scribbles]
Fri Mar 06: Lab 7b: Dynamic programming — [solutions]
Mon Mar 09: Guided problem set 6 due at 9pm
Tue Mar 10: Homework 6 due at 9pm — [solutions]

Tue Mar 10: Lecture: More dynamic programming: edit distance, subset sum — [scribbles]
Wed Mar 11: Lab 8a: More dynamic programming — [solutions]
Thu Mar 12: Lecture: Dynamic programming: MIS in trees, memoization and edit distance — [scribbles]
Fri Mar 13: Lab 8b: Dynamic programming: fire and ash — [solutions]
Fri Mar 13: ⚠️ Drop deadline (11:59pm)
Mar 14–22: Spring break — GPS and HW 7 due one week later than usual
Mon Mar 23: Guided problem set 7 due at 9pm
Tue Mar 24: Homework 7 due at 9pm — [solutions]

Mar 14–22 — Spring Break 🌷

Tue Mar 24: Lecture: Graphs, basic search — [scribbles]
Wed Mar 25: Lab 9a: Graph modeling — [solutions, graph layering notes]
Thu Mar 26: Lecture: DFS, topological sort, and strong connected components — [scribbles]
Fri Mar 27: Lab 9b: More graph modeling — [solutions]
Mon Mar 30: Guided problem set 8 due at 9pm
Tue Mar 31: Homework 8 due at 9pm — [solutions]

Tue Mar 31: Lecture: BFS and shortest paths — [scribbles]
Wed Apr 01: Lab 10a: Shortest paths — [solutions]
Thu Apr 02: Lecture: Shortest paths with negative lengths via DP; All-pairs shortest paths via DP — [scribbles]
Fri Apr 03: Lab 10b: More shortest paths — [solutions]
Mon Apr 06: Guided problem set 9 due at 9pm
Tue Apr 07: Homework 9 due at 9pm — [solutions]

Tue Apr 07: Lecture: Greedy algorithms; minimum spanning trees — [scribbles]
Wed Apr 08: Lab 11: Greedy algorithms and/or minimum spanning trees — [solutions]
Thu Apr 09: No lecture: Optional review for Midterm 2
Fri Apr 10: No lab: Optional review for Midterm 2
Mon Apr 13: Midterm 2: 7pm–9pm — [solutions]
Tue Apr 14: Conflict Midterm 2: (time TBA) — [solutions]

Tue Apr 14: Lecture: Polynomial time reductions: cliques and friends — [scribbles]
Wed Apr 15: Lab 12a: Reductions — [solutions]
Thu Apr 16: Lecture: P vs NP, NP-hardness, 3SAT, reduction to max independent set — [scribbles]
Fri Apr 17: Lab 12b: NP-hardness proofs — [solutions]
Mon Apr 20: Guided problem set 10 due at 9pm
Tue Apr 21: Homework 10 due at 9pm — [solutions]

Tue Apr 21: Lecture: NP-hardness: 3SAT to 3Color, 3SAT to HamiltonianCycle — [scribbles]
Wed Apr 22: Lab 13a: The NP-hardness proofs strike back — [solutions]
Thu Apr 23: Lecture: NP-hardness: VertexCover to SubsetSum, why bother, choosing which problem to reduce from — [scribbles]
Fri Apr 24: Lab 13b: The return of the NP-hardness proofs — [solutions]
Mon Apr 27: No guided problem set this week
Tue Apr 28: Homework 11 due at 9pm — [solutions]

Tue Apr 28: Lecture: Undecidability: code is data, the halting problem — [scribbles]
Wed Apr 29: Lab 14a: Undecidability via diagonalization — [solutions]
Thu Apr 30: Lecture: Undecidability: reductions and Rice's theorem — [scribbles]
Fri May 01: Lab 14b: Undecidability via reductions and Rice's theorem — [solutions]
Mon May 04: Guided problem set 11 due at 9pm
Tue May 05: Homework 12 due at 9pm — [solutions]

Tue May 05: Lecture: Wrap-up and optional final exam review — [scribbles]
Wed May 06: No lab: Optional review for final exam
Thu May 07: Reading day; FLEX feedback due
Wed May 13: Conflict Final Exam: (date tentative; time TBA) — [solutions]
Thu May 14: Final Exam: 7pm–10pm — [solutions]

Tue Jan 20: Lecture: Course goals and administrivia; strings and induction — [scribbles, video, induction notes, helpful advice on writing proofs]
Wed Jan 21: Lab 1a: String induction — [solutions, induction notes, helpful advice on writing proofs]
Thu Jan 22: Lecture: Languages and regular expressions — [scribbles, video]
Fri Jan 23: Lab 1b: Regular expressions — [solutions]
Mon Jan 26: Guided problem set 1 due at 9pm
Tue Jan 27: Homework 1 due at 9pm — [solutions]