Homeworks are due at 10:20AM before the start of class digitally through Gradescope. Unfortunately, due to a lack of a physical hand-in bin this season, we cannot accept baked goods alongside submissions.

Your Banner ID should appear on all pages; please do not include your name anywhere.

Before submitting any assignment, please make sure you read and subscribe to the class collaboration policy (linked below as Homework 0).

__Late submission policy:__ Each student is given 4 late day passes to extend the submission deadlines of homeworks and midterms. However, no more than 2 passes may be applied to a given deadline.
Additional late day passes may be granted by the instructors in consideration of extenuating circumstances (e.g., illness). Requests should be submitted to the instructors at least 24 before a deadline via a Google form.

# | Homework Topic | Out | In | Solutions |
---|---|---|---|---|

0 | Collaboration Policy | Sep 10 | Sep 17 | --- |

0 | Review of Discrete Math | Sep 11 | Sep 17 | Solutions |

1 | DFAs and NFAs | Sep 17 | Sep 24 | Solutions |

2 | Regular Languages and Pumping Lemma | Sep 24 | Oct 1 | Solutions |

3 | Context-Free Grammars and Pumping Lemma | Oct 1 | Oct 8 | Solutions |

4 | Turing Machines | Oct 8 | Oct 15 | Solutions |

- | Midterm 1 | Oct 15 | Oct 22 | Solutions |

5 | Turing Decidability and Rice's Theorem | Oct 22 | Oct 29 | Solutions |

6 | Runtime, P and NP | Oct 29 | Nov 5 | Solutions |

7 | NP and NP-Completeness | Nov 10 | Nov 17 | Solutions |

8 | PSPACE | Nov 17 | Nov 24 | Solutions |

- | Midterm 2 | Dec 2 | Dec 9 |