CS 374 A

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 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]