# 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*