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