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 pdf | Sep 5 | Sep 12 | Solutions |
| 1 | DFAs and NFAs tex | Sep 12 | Sep 19 | Solutions |
| 2 | Regular Expressions and Pumping Lemma tex | Sep 19 | Sep 26 | Solutions |
| 3 | Context-Free Grammars/Languages and PDAs tex | Sep 26 | Oct 3 | Solutions |
| 4 | Pumpimg Lemma for CFLs and Turing Machines tex | Oct 3 | Oct 10 | Solutions |
| 5 | Turing Machine variations and Reducibility tex | Oct 10 | Oct 17 | Solutions |
| - | Midterm | Oct 17 | Oct 24 | Solutions |
| 6 | Turing Decidability and Undecidability tex | Oct 24 | Oct 31 | Solutions | 7 | P and NP tex | Oct 31 | Nov 7 | Solutions |
| 8 | NP-Completeness tex | Nov 7 | Nov 14 | Solutions |
| 9 | Space Complexity and PSPACE-Complete Problems tex | Nov 14 | Nov 21 | Solutions |
| 10 | L and NL Completeness | Nov 21 | Dec 4 | Solutions |
| - | Final Exam | TBA | - | - |