CS 374 A


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 extended due date. (Links to future homeworks and solutions are placeholders; topics of future homeworks are subject to change.)

Tue Aug 29
Homework 1: Strings and induction [solutions]
Wed Sep 6
Homework 2: Regular expressions and DFAs [solutions]
Tue Sep 12
Homework 3: Fooling sets, Regular or not? [solutions]
Tue Sep 19
Homework 4: Language transformations and CFGs [solutions]

Tue Oct 3
Homework 5: Divide and conquer [solutions]
Tue Oct 10
Homework 6: Dynamic programming [solutions]
Tue Oct 17
Homework 7: More dynamic programming [solutions]
Tue Oct 24
Homework 8: Graph algorithms [solutions]
Tue 🎃ct 31
Homework 9: More graph algorithms [solutions]

Tue Nov 14
Homework 10: NP-hardness [solutions]
Tue Nov 28
Homework 11: More NP-hardness [solutions]
Tue Dec 5
Homework 12: Undecidability (optional) — [solutions]