Homeworks are due at 10:20AM before the start of class.
Homeworks must be typeset. You can include hand-drawn diagrams as part of the submission whenever appropriate. We encourage you to use LaTeX for typesetting your solution, using this LaTeX template.
Submissions have to be handed in using Gradescope. Use your Brown University email when registering. If this is your first time using Gradscope, please refer to the Gradescope guide.
HW assignments (with LaTeX code) will also be released on Ed. Solutions will be posted on Ed Only. There will also be a post there with comments/clarifications/FAQs.
Before submitting any assignment, please make sure you read and subscribe to the class collaboration policy (linked below in the syllabus).
Late submission policy: Please refer to the course syllabus for the collaboration and late submission policy.
| # | Homework Topic | Out | In |
|---|---|---|---|
| 0 | Sign the Syllabus | Sep 12 | Sep 24 |
| 1 | DFAs and Basic Proofs tex | Sep 10 | Sep 17 |
| 2 | NFAs + RegEx + Pumping Lemma tex | Sep 17 | Sep 24 |
| 3 | Context-Free Grammars/Languages and PDAs tex | Sep 24 | Oct 1 |
| 4 | Pumpimg Lemma for CFLs and Turing Machines tex | Oct 1 | Oct 8 |
| 5 | Turing Machine variations and Decidability/Undecidability tex | Oct 8 | Oct 15 |
| 6 | Reducibility tex | Oct 15 | Oct 22 |
| - | Midterm | Oct 27 | --- |
| 7 | P and NP SAT variations tex | Oct 29 | Nov 5 |
| 8 | NP-Completeness tex | Nov 5 | Nov 12 |
| 9 | Space Complexity and PSPACE-complete problems tex | Nov 12 | Nov 19 |
| 10 | L - NL and NL-completeness + Intractability tex | Nov 19 | Dec 3rd |
| - | Final Exam | Dec 16 | --- |