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

• Textbooks

• Videos

• Websites

• Articles

Prerequisites

This course has the following prerequisites:

• Discrete Structures for CS

• Logic in CS

This course is a prerequisite for:

• Design & Analysis of Algorithms

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

Articles

• The Computational Complexity Blog
• Gödel's Lost Letter and P = NP
• The Physics Arxiv blog on P/NP