Theory of Computation
Overview
TOC deals with computers as a topic of abstraction. Using the tools from Discrete Mathematics, we construct rigorous proofs for computational systems and analyze what problems can be solved by a computer. This subject is also referred to as Automata Theory and includes theoretical models such as Finite State Machines, Turing Machines and more. The ideas presented here are perhaps some of the most abstract, yet elegant pieces of information you will come across in your journey in CS.
Navigation
Prerequisites
This course has the following prerequisites:
This course is a prerequisite for:
Textbooks
| Title | Author(s) | Edition |
|---|---|---|
| Elements of the Theory of Computation | Lewis & Papadimitriou | 2nd (1998) |
| Introduction to Automata Theory, Languages & Computation | Hopcroft, Motwani & Ullman | 3rd (2007) |
| Introduction to Languages and The Theory of Computation | John. C Martin | 4th (2010) |
| Introduction to the Theory of Computation | Sipser | 3rd (2013) |
Videos
- NP-Hard and NP-Complete Problems, Abdul Bari
- P vs. NP and the Computational Complexity Zoo, Hackerdashery
- Introduction to Theory of Computation, Neso Academy (Full Course)
- Theory of Computation part-1, Knowledge Gate (Full Course)
- Theory of Computation part-1, Knowledge Gate (Full Course)
- Theory Of Computation or Automata Theory, Ravindrababu Ravula (Full Course)
Websites
- Index of TOC, Prof. K. R. Chowdhary
- Shtetl-Optimized, Scott Aaronson
- Old Exams and Quizzes, Marvin K. Nakayama