This section contains discussion materials and problems solved by students during the recitation sessions.
Recitation files.
| SES # |
Topics |
| R1 |
Math Review (PDF) |
| R2 |
DFAs and NFAs (PDF) |
| R3 |
Regular Expressions and Non-Regular Languages (PDF) |
| R4 |
Quiz Questions and Automata Wrap-up (PDF) |
| R5 |
Turing Machines (PDF) |
| R6 |
Undecidability (PDF) |
| R7 |
Counter and Stack Machines, Reducibility, Rice's Theorem (PDF) |
| R8 |
Quiz 2 Questions and Computability Wrap-up (PDF) |
| R9 |
P and NP (PDF) |
| R10 |
Poly-Time Reductions |
| R11 |
NP-Completeness (PDF) |
| R12 |
Quiz 3 Questions and End of Time Complexity |
| R13 |
Space Complexity III (PDF) |
| R14 |
Probabilistic Complexity and Interactive Proofs |