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