d
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 tex | Sep 25 | Oct 2 | Solutions |
| 4 | Pumpimg Lemma for CFLs and Turing Machines tex | Oct 2 | Oct 9 | Solutions |
| 5 | Turing Machine variations and Reducibility tex | Oct 9 | Oct 16 | Solutions |
| - | Midterm | Oct 21 | --- | --- |
| 6 | Turing Decidability and Undecidability tex | Oct 23 | Oct 30 | Solutions | 7 | Reductions and Algorithms tex | Oct 30 | Nov 6 | Solutions |
| 8 | P and NP tex | Nov 6 | Nov 13 | Solutions |
| 9 | NP-Completeness tex | Nov 13 | Nov 20 | Solutions |
| 10 | NP, co-NP, and PSPACE tex | Nov 25 | Dec 4th | Solutions |
| - | Final Exam | TBA | --- | --- |