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 9 | Sep 25 | --- |
| 0 | Review of Discrete Math pdf | Sep 4 | Sep 11 | Solutions |
| 1 | DFAs and NFAs tex | Sep 11 | Sep 18 | Solutions |
| 2 | Regular Expressions and Pumping Lemma tex | Sep 18 | Sep 25 | Solutions |
| 3 | Context-Free Grammars/Languages and PDAs | Sep 25 | Oct 2 | Solutions |
| 4 | Pumpimg Lemma for CFLs and Turing Machines | Oct 2 | Oct 9 | Solutions |
| 5 | Turing Machine variations and Reducibility | Oct 9 | Oct 16 | Solutions |
| - | Midterm | Oct 21 | --- | Solutions |
| 6 | Turing Decidability and Undecidability | Oct 23 | Oct 30 | Solutions | 7 | P and NP | Oct 30 | Nov 6 | Solutions |
| 8 | NP-Completeness | Nov 6 | Nov 13 | Solutions |
| 9 | Space Complexity and PSPACE-Complete Problems | Nov 13 | Nov 20 | Solutions |
| 10 | NP, co-NP and PSPACE | Nov 25 | Dec 4th | Solutions |
| - | Final Exam | TBA | --- | --- |