CS-701 Theory of Computation
Q & A
Online Test
Course Category: Computer Science/Information Technology
Course Level: Graduate
Credit Hours: 3
Pre-requisites: CS402, MTH202
Share this page on:
CS701 Handouts version 1
Course Contents:
Introduction, Set Thoery, Sequences, Tuples, Functions, Relations, Graphs, Turing Machines, Enumerators, Dovetailing, The Church-Turing Thesis, Hilbert's Tenth Problem, Decidable Languages, The Acceptance Problem for DFAs, The Halting Problem, Universal TM, Undicidability of the Halting Problem, Linear Bounded Automata, Computation Histories, Context Free Grammars, Russell's Paradox, Emptiness Problem, Post Correspondence Problem, Computable Functions, Reducibility, Recursion Theorem, Logical Theories, Godel's Theorem, Oracles, Turing Reducibility, A definition of Information, Incompressible Strings, Complexity Theory, Big Oh and Little Oh Notations, Time Complexity, Non-Deterministic Time, The Class P, The Class NP, Polynomial Time Verifiers, Subset Sum Problem, Satisfiability, NP-Completness, 3-Color Problem, The Cook-Levin Theorem, Independent Sets Problem, Clique, Vertex Cover, Hamiltonian Path Problem, The Subset Sum Problem, The Traveling Salesman Problem, Space Complexity, Relationship between Space and Time Complexity, PSPACE-Completeness, TQBF, Prove that TQBF is PSPACE-Complete, FORMULA-GAME, Generalized Geography, LOGSPACE Transducer, Prove the Theorem: NL = co-NL.
Course Instructor

Dr. Sarmad Abbasi
Ph.D Computer Science
Rutgers University, USA

Book Title: Introduction to the Theory of Computation by Michael Sipser

Solution ( Introduction to the Theory of Computation )