The objective of this course is provide an introduction to the

**theory of computation**covering the following three branches of theoretical computer science:- Automata Theory
- Formalization of the notion of problems via
**formal languages** - Formalization of the notion of computation using "abstract computing devices" called
**automata** - Understanding a hierarchy of classes of problems or formal languages (regular, context-free, context-sensitive, decidable, and undecidable)
- Understanding a hierarchy of classes of automata (finite automata, pushdown automata, and Turing machines)
- Understanding applications to pattern matching, parsing, and programming languages

- Formalization of the notion of problems via
- Computability Theory
- Understanding Church-Turing thesis (Turing machines as a notion of "general-purpose computers")
- Understanding the concept of
**reduction**, i.e., solving a problem using a solution (abstract device) for a different problem - Understanding the concept of
**undecidability**, i.e., when a problem can not be solved using computers

- Complexity Theory
**Complexity classes**: how to classify decidable problems based on their time and space requirements- Complexity classes P and NP
- When a problem is called
**intractable**(NP-completeness) - Using reductions to prove problems intractable

- Teacher: Ashutosh Trivedi