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. **Lab write-ups count towards your homework grade.**

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

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

0 | Collaboration Policy | Sep 5 | Sep 12 | --- |

1 | Review of Discrete Math | Sep 5 | Sep 12 | Solutions |

2 | DFAs and NFAs | Sep 12 | Sep 19 | Solutions |

3 | Regular Languages and Pumping Lemma | Sep 19 | Sep 26 | Solutions |

4 | Context-Free Grammars and Pumping Lemma | Sep 26 | Oct 3 | Solutions |

--- | Midterm 1 |
Oct 3 | --- | Solutions |

5 | Turing Machines | Oct 10 | Oct 17 | Solutions |

6 | Decidability and Undecidability, Rice's Theorem | Oct 17 | Oct 24 | Solutions |

7 | Turing Recognizability and Decidability, Time Complexity | Oct 24 | Oct 31 | Solutions |

8 | NP-Completeness | Oct 31 | Nov 7 | Solutions |

9 | More NP-Completeness | Nov 7 | Nov 14 | Solutions |

--- | Midterm 2 |
Nov 14 | Nov 21 | Solutions |

10 | Space Complexity | Nov 21 | Dec 5 | Solutions |

--- | Final Exam |
Dec 16 | --- | --- |