# Theory of Computation

## Overview

TOC deals with computers as a topic of abstraction. Using the tools from Discrete Mathematics, we construct rigorous [`proofs`](https://en.wikipedia.org/wiki/Mathematical_proof) 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`](https://brilliant.org/wiki/finite-state-machines/), [`Turing Machines`](https://brilliant.org/wiki/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](#prerequisites)
* [Textbooks](#textbooks)
* [Videos](#videos)
* [Websites](#websites)
* [Articles](#articles)

## Prerequisites

This course has the following prerequisites:

* [Discrete Structures for CS](https://bpdc-acm.gitbook.io/openlib-cs/courses/csf222)
* [Logic in CS](https://bpdc-acm.gitbook.io/openlib-cs/courses/csf214)

This course is a prerequisite for:

* [Design & Analysis of Algorithms](https://bpdc-acm.gitbook.io/openlib-cs/courses/csf364)

## Textbooks

| Title                                                                                                                          | Author(s)                  |   Edition  |
| ------------------------------------------------------------------------------------------------------------------------------ | -------------------------- | :--------: |
| [Elements of the Theory of Computation](https://drive.google.com/open?id=1z_DeXa24LtBEjobo3FgygoVx_qFzIyd1)                    | Lewis & Papadimitriou      | 2nd (1998) |
| [Introduction to Automata Theory, Languages & Computation](https://drive.google.com/open?id=1J37lIwspju4mnKOsiOgW2xKJig_ckknx) | Hopcroft, Motwani & Ullman | 3rd (2007) |
| [Introduction to Languages and The Theory of Computation](https://drive.google.com/open?id=1Eoz_fHaEL73upWM88VLYgq9OGfo2yY1U)  | John. C Martin             | 4th (2010) |
| [Introduction to the Theory of Computation](https://drive.google.com/open?id=1LgHU3Eq1xNsTWgqkkFDd-DoX4Iczlbrt)                | Sipser                     | 3rd (2013) |

## Videos

* [NP-Hard and NP-Complete Problems, *Abdul Bari*](https://www.youtube.com/watch?v=e2cF8a5aAhE\&t=10s)
* [P vs. NP and the Computational Complexity Zoo, *Hackerdashery*](https://www.youtube.com/watch?v=YX40hbAHx3s)
* [Introduction to Theory of Computation, *Neso Academy*](https://www.youtube.com/watch?v=58N2N7zJGrQ\&list=PLBlnK6fEyqRgp46KUv4ZY69yXmpwKOIev) *(Full Course)*
* [Theory of Computation part-1, *Knowledge Gate*](https://www.youtube.com/watch?v=i6JhheV01dU\&list=PLmXKhU9FNesQe1bKW0w7APAGiJVlQP8Zx) *(Full Course)*
* [Theory of Computation part-1, *Knowledge Gate*](https://www.youtube.com/watch?v=00cXiux2Kjk\&list=PLmXKhU9FNesSdCsn6YQqu9DmXRMsYdZ2T) *(Full Course)*
* [Theory Of Computation or Automata Theory, *Ravindrababu Ravula*](https://www.youtube.com/watch?v=eqCkkC9A0Q4\&list=PLEbnTDJUr_IdM___FmDFBJBz0zCsOFxfK) *(Full Course)*

## Websites

* [Index of TOC, *Prof. K. R. Chowdhary*](http://www.krchowdhary.com/toc/)
* [Shtetl-Optimized, *Scott Aaronson*](https://www.scottaaronson.com/blog/)
* [Old Exams and Quizzes, *Marvin K. Nakayama*](https://web.njit.edu/~marvin/cs341/oldexams/)

## Articles

* [The Computational Complexity Blog](https://blog.computationalcomplexity.org/)
* [Gödel's Lost Letter and P = NP ](https://rjlipton.wordpress.com/)
* [The Physics Arxiv blog on P/NP](https://medium.com/the-physics-arxiv-blog/the-astounding-link-between-the-p-np-problem-and-the-quantum-nature-of-universe-7ef5eea6fd7a)