CS701 : Theory of Computation

Course Overview

Course Synopsis

This is the first pure course in theoretical computer science. It discusses some of the fundamental questions about computation. It starts with an overview of the concepts in theory of automata. Then discusses computability theory in detail. After developing concepts in computability theory the course moves forward to complexity theory. Complexity theory is subdivided into time and space complexity. The course first discusses time complexity and after that space complexity is covered in detail.

Course Learning Outcomes

At the completion of the course, you should be able to answer the following questions:

  • What is computation?
  • Is there a universal model of computation?
  • Can everything be computed?
  • Can we identify problems that are not computable?
  • What resources are needed to perform a certain computation?
  • Can we identify computationally hard problems?

Course Calendar

Introduction1Sipser (2005)
Set Thoery, Sequences, Tuples, Functions, Relations and Graphs2do.
Turing Machine and its Language3do.
Designing Turing Machines4do.
Variants of Turing Machines5do.
Enumerators, Dovetailing, The Church-Turing Thesis, Hilbert's Tenth Problem6do.
Decidable Languages, The Acceptance Problem for DFAs7do.
The Halting Problem, Universal TM8do.
Assignment No. 1
Undicidability of the Halting Problem9do.
Linear Bounded Automata, Computation Histories, Context Free Grammars10do.
Russell's Paradox, Emptiness Problem11do.
Post Correspondence Problem, Computable Functions12do.
Computable Functions (Cont.), Reducibility13do.
Reducibility (Cont.), Recursion Theorem14do.
Recursion Theorem (Cont.), Logical Theories15do.
Logical Theories (Cont.)16do.
Assignment No. 2
Logical Theories (Cont.), Godel's Theorem17do.
Oracles, Turing Reducibility18do.
A definition of Information, Incompressible Strings19do.
Incompressible Strings (Cont.), Complexity Theory20do.
Big Oh and Little Oh Notations, Time Complexity21do.
Non-Deterministic Time, The Class P, The Class NP22do.
Mid-term Examination
The Class NP (Cont.), Polynomial Time Verifiers23do.
The Class NP (Cont.)24do.
Subset Sum Problem, Satisfiability25do.
Satisfiability (Cont.), 3-Color26do.
Satisfiability (Cont.)27do.
The Cook-Levin Theorem28do.
NP-Completeness, Independent Sets29do.
Independent Sets (Cont.), NP-Completeness (Cont.), Clique, Vertex Cover30do.
Assignment No. 3
Hamiltonian Path Problem31do.
NP-Completeness (Cont.)32do.
The Subset Sum Problem33do.
The Traveling Salesman Problem34do.
An Approximation Algorithm for TSP Problem35do.
Space Complexity36do.
Space Complexity (Cont.)37do.
Relationship between Space and Time Complexity, PSPACE-Completeness38do.
Course viva
TQBF, Prove that TQBF is PSPACE-Complete39do.
TQBF (Cont.), FORMULA-GAME, Generalized Geography40do.
Generalized Geography (Cont.)41do.
LOGSPACE Transducer42do.
Prove the Theorem: NL = co-NL43do.
Prove the Theorem: NL = co-NL (Cont.)44do.
Overview of the course covered45do.
Final-term Examination
Back to Top