CSE 3315 - Theory of Computation
⭓Description
This is the course page for CSE 3315 - Theory of Computation in Summer 2025. Here you’ll find class notes and other helpful resources. All assignments and announcements will be posted on Canvas.
Instructor Office Hours
| Days | Time | Location |
|---|---|---|
| MoWe | 1PM - 2PM | ERB 556A |
| TuTh | 3PM - 4PM | ERB 556A |
| Fri | 9AM - 10AM | Teams |
Teaching Assistants
- Roman Strukov (rxs6055 (at) mavs (dot) uta (dot) edu)
Office Hours
| Days | Time | Location |
|---|---|---|
| TuTh | 4PM - 6PM | ERB 309 (Teams Preferred) |
⭓Course Materials
Books
- Michael Sipser, Introduction to the Theory of Computation, Cengage, 2013.
- Richard Hammack, Book of Proof, Self published, 2018.
- Daniel J. Velleman, How To Prove It, Cambridge University Press, 2019.
- Avi Wigderson, Mathematics and Computation, Online, 2018.
- Kenneth H. Rosen, Discrete Mathematics and Its Applications, McGraw-Hill, 2018.
Resources
⭓Schedule
This schedule is tentative and may change.
| Date | Topic | Materials |
|---|---|---|
| June 2 | Course Introduction and Background |
|
| June 4 | Finite Automata, Regular Operations and Closure |
|
| June 9 | Nondeterminism and Regular Expressions |
|
| June 11 | Regular Expressions, FSA Equivalence |
|
| June 16 | FSA Equivalence, Pumping Lemma |
|
| June 18 | Pumping Lemma |
|
| June 23 | Exam 1 |
|
| June 25 | State Minimization, Countability |
|
| June 30 | Context-Free Grammars and Ambiguity |
|
| July 2 | Chomsky Normal Form, CFL Pumping Lemma |
|
| July 7 | CFL Pumping Lemma Examples, Pushdown Automata |
|
| July 9 | Turing Machines |
|
| July 14 | Turing Machines |
|
| July 16 | Exam 2 |
|
| July 21 | Turing Machine Variants, Decidable Languages |
|
| July 23 | Decidable Languages, Halting Problem |
|
| July 28 | Time Complexity, Class P-time |
|
| July 30 | NP and NP-Completeness |
|
| August 4 | Reductions |
|
| August 6 | Wrap-up and Final Exam Review |
|
| August 7 | Final Exam |
|