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.)
- A LaTeX template is available for typsetting homework solutions.
- Standard grading rubrics are available for many problem types.
- Don't forget to read the homework policies
- Tue Jan 27
- Homework 1: Strings and induction due at 9pm — [solutions]
- Tue Feb 03
- Homework 2: Regular expressions and DFAs due at 9pm — [solutions]
- Tue Feb 10
- Homework 3: Fooling sets and inferring regularity due at 9pm — [solutions]
- Tue Feb 17
- Homework 4: Language transformations and CFGs due at 9pm — [solutions]
- Tue Mar 03
- Homework 5: Divide and conquer due at 9pm — [solutions]
- Tue Mar 10
- Homework 6: Dynamic programming due at 9pm — [solutions]
- Tue Mar 24
- Homework 7: More dynamic programming due at 9pm — [solutions]
- Tue Mar 31
- Homework 8: Graph algorithms due at 9pm — [solutions]
- Tue Apr 07
- Homework 9: More graph algorithms due at 9pm — [solutions]
- Tue Apr 21
- Homework 10: Polynomial time reductions and NP-hardness due at 9pm — [solutions]
- Tue Apr 28
- Homework 11: More NP-hardness due at 9pm — [solutions]
- Tue May 05
- Homework 12: Undecidability due at 9pm — [solutions]