CS 374 A, Fall 2025

Homeworks


Written homeworks are due every Tuesday at 9pm unless announced otherwise. We post each week's homework at least one full week before its due date; we post solutions at most a day after the due date. (Links to future homeworks and solutions are placeholders; topics of future homeworks are subject to change.)


Wed Sep 3
Homework 1: Strings and induction [solutions]
Tue Sep 9
Homework 2: Regular expressions and DFAs [solutions]
Tue Sep 16
Homework 3: Fooling sets, Regular or not? [solutions]
Tue Sep 23
Homework 4: Language transformations and CFGs [solutions]
Tue Sep 30
No homework — Midterm 1

Tue Oct 7
Homework 5: Divide and conquer [solutions]
Tue Oct 14
Homework 6: Dynamic programming [solutions]
Tue Oct 21
Homework 7: More dynamic programming [solutions]
Tue Oct 28
Homework 8: Graph algorithms [solutions]
Tue Nov 4
Homework 9: More graph algorithms [solutions]
Tue Nov 11
No homework — Midterm 2

Tue Nov 18
Homework 10: NP-hardness [solutions]
Tue Nov 25
No homework — Thanksgiving break
Tue Dec 2
Homework 11: More NP-hardness [solutions]
Tue Dec 9
Homework 12: Undecidability (optional) — [solutions]