en:courses:2020

—- data course —-

Code: 2020 Title: Theory of Computation English Title: Theory of Computation Level: MicroMaster Field: Software Engineering Credits: 3 Type: Theoretical Category: Specialized Priority: 40 Prerequisite: Data Structures and Algorithms Co-requisite: – Image: math.png ID: 2020 Instructor: Mohammad Izadi Term: Summer 2025 Schedule: –

Objective

The objective of this course is to familiarize MicroMaster Algorithm students with the theoretical foundations of problem computability and, for computable problems, the fundamentals of algorithm science and complexity analysis. Topics include various computational models, their computational capabilities, their computational properties, and their applications. Other topics include concepts of computability, decidability, and the Church-Turing thesis regarding algorithms. Special emphasis will be placed on the theory of algorithm complexity and the relationships between complexity classes.

Topics

Preliminaries (2 sessions)
- Introduction to main concepts and history of computation theory, complexity theory, and formal languages/automata theory
- Supplementary topics in logic and set algebra, countable sets, languages and grammars
Finite Automata and Regular Languages (4 sessions)
- Deterministic and non-deterministic finite acceptors, regular languages and regular expressions
- Right-linear and left-linear grammars, regular grammars, Pumping lemma for regular languages
Context-Free Languages and Pushdown Automata (4 sessions)
- Context-free grammars, context-free languages
- Leftmost and rightmost derivations, parse trees, ambiguous and unambiguous grammars, inherently ambiguous/unambiguous languages
- Simplification of context-free grammars and their Chomsky/Greibach normal forms
- Pushdown automata, equivalence between pushdown automata and context-free grammars, deterministic pushdown automata
- Deterministic context-free languages, non-context-free languages, Pumping lemma for context-free languages
Computability (4 sessions)
- Turing machines, Church-Turing thesis
- Decidability and undecidability, recognizability and unrecognizability of languages and problems
- Halting problem, Post correspondence problem, and other examples of problems from decidability/recognizability perspective
- Problem reduction methods for proving (un)decidability or (un)recognizability
Computational Complexity Theory (4 sessions)
- Time complexity of algorithms, polynomial-time reduction
- Time complexity classes including P, NP and Co-NP classes, complete problem definition with emphasis on NP-complete problems
- Methods for proving NP-completeness, Cook-Levin theorem
- Examples of NP-complete problems (Hamiltonian cycle, vertex cover, subset sum, etc.)
- Space complexity of problems and related classes (logarithmic space, polynomial space and their complements)
- Relationships between space complexity classes
- Relationships between time and space complexity classes

Assessment

Homework assignments: 6 points
Final exam: 14 points

References

M. Sipser. Introduction to the Theory of Computation. 3rd Edition, Cengage Learning, 2013.
J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to automata theory, languages, and computation. 2nd Edition, Addison-Wesley, 2001.
J. E. Hopcroft and J. D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley, 1979.