Assignments
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. There will be 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 | Solutions |
|---|---|---|---|---|
| 0 | Sign the Syllabus | Sep 5 | Sep 12 | --- |
| 0 | Review of Discrete Math | Sep 5 | Sep 12 | Solutions |
| 1 | DFAs and NFAs | Sep 12 | Sep 19 | Solutions |
| 2 | Regular Expressions and Pumping Lemma | Sep 19 | Sep 26 | Solutions |
| 3 | Context-Free Grammars/Languages and PDAs | Sep 26 | Oct 3 | Solutions |
| 4 | Pumpimg Lemma for CFLs and Turing Machines | Oct 3 | Oct 10 | Solutions |
| 5 | Turing Machine variations and Reducibility | Oct 10 | Oct 17 | Solutions |
| - | Midterm | Oct 17 | Oct 24 | Solutions |
| 6 | Turing Decidability and Undecidability | Oct 24 | Oct 31 | Solutions | 7 | P and NP | Oct 31 | Nov 7 | Solutions |
| 8 | NP-Completeness | Nov 7 | Nov 14 | Solutions |
| 9 | Space Complexity and PSPACE-Complete Problems | Nov 14 | Nov 21 | Solutions |
| 10 | NP, co-NP and PSPACE | Nov 21 | Dec 4th | Solutions |
| - | Final Exam | TBA | - | - |