Instructor: Stacy Patterson sep@cs.rpi.edu
Office Hours: W R 3:00pm - 4:00pm or by appointment
Lectures: M R 12:20pm - 2:10pm
Lectures will be delivered via WebEx Meetings during the scheduled lecture time. They will also be recorded, and the links to the recorded lectures will be posted in Submitty.
Homework and exams are managed through Gradescope.
Office hours are managed through the Submitty Office Hours Queue. The access code is toc.
See the syllabus for details about the course policies, grading, etc.
This course covers the formal foundations of computability and complexity. We aim to answer fundamental questions about what problems can be solved and what problems cannot be solved, and what problems can be solved given our limited resources. Topics include: the Church-Turing thesis; variations of Turing Machines; decidability; the Halting Problem; reducibility; the Recursion Theorem; time and space complexity; intractability; NP-completeness; and Cook’s theorem. We will also discuss some unconventional computing models, such as optical computing and DNA computing.
The Spring 2021 offering of CSCI 4962 counts in the Theory and Algorithms concentration area for the B.S. in Computer Science.
The Spring 2021 offering of CSCI 6962 counts in the Theory depth area for MS and PhD students.
This class will be offered online in the spring. Lectures will be livestreamed and will also be recorded for offline vieweing.
There will be no lecture on exam days.
| 1/25/21 | Course overview, DFAs, Regular languages | Sipser 1.1 | |
| 1/27/21 | NFAs | Sipser 1.2 | |
| 2/1/21 | Regular expressions, the pumping lemma | Sipser 1.3, 1.4 | |
| 2/4/21 | Context-Free Grammars, PDAs | Sipser 2.1, 2.2 | |
| 2/8/21 | Non-context-free langauges, Turing machines | Sipser 2.3, 3.1 | |
| 2/11/21 | Turing machine variants | Sipser 3.2 | |
| 2/15/21 | No class | ||
| 2/18/21 | Church-Turing Thesis, Definition of algorithms, Decidable Languages | Sipser 3.3, 4.1 | Slides: .pptx .pdf |
| 2/22/21 | Undecidability | Sipser 4.2 | Slides: .pptx .pdf |
| 2/25/21 | Exam 1 - No lecture | ||
| 3/1/21 | Undecidable problems, reducibility, mapping reducibility | Sipser 4.2, 5.1 | Slides: .pptx .pdf |
| 3/4/21 | Mapping reducibility, The Post Correspondence Problem | Sipser 5.2, 5.3 | Slides: .pptx .pdf Reduction steps |
| 3/8/21 | Rice's theorem, Recursion theorem, Measuring complexity | Sipser 6.1, 7.1 | Slides: .pptx .pdf |
| 3/11/21 | The Class P, The Class NP | Sipser 7.2, 7.3 | Slides: .pptx .pdf |
| 3/15/21 | Polynomial Time Reducibility, NP Completeness | Sipser 7.4, 7.5 | Slides: .pptx .pdf |
| 3/18/21 | The Cook-Levin Theorem | Sipser 7.4 | Slides: .pptx .pdf |
| 3/22/21 | Space Complexity, PSPACE | Sipser 8.1, 8.2, 8.3 | Slides: .pptx .pdf |
| 3/25/21 | PSPACE-completeness, L, NL | Sipser 8.3, 8.4 | Slides: .pptx .pdf |
| 3/29/21 | Exam 2 - No lecture | ||
| 4/1/21 | No lecture | ||
| 4/5/21 | L, NL, NL-completeness | Sipser: 8.3, 8.4, 8.5 | Slides: .pptx .pdf |
| 4/8/21 | Hierarchy Theorems | Sipser: 9.1 | Slides: .pptx .pdf |
| 4/12/21 | Probabilistic Algorithms | Sipser: 10.2 | Slides: .pptx .pdf |
| 4/15/21 | Quantum Computing | ||
| 4/19/21 | Quantum Computing | ||
| 4/22/21 | Quantum Computing | ||
| 4/26/21 | Student Presentations | ||
| 4/29/21 | Student Presentations | ||
| 5/3/21 | Exam 3 | Exam 3 topics |