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
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.
 CS-701 Handouts Version 1  CS 701 Midterm  CS 701 Midterm  CS701 - Solved Questions Ans  CS701 - Solved Questions  CS701 Final Solutions  CS701 Final Term QA  CS701 Mid Term Papers 2015  CS701 Paper with MCQs on 31.01.2015  CS701_Final_Term_2015_Mega_File  CS701_midterm  CS701_sipser_chapter8_solution  Fall 2014_CS701_2  Fall 2014_CS701_3  Fall 2014_CS701_4  Fall 2014_CS701_6 CS701_Final_Term_Solution - Part I CS701_Final_Term_Solution - Part II CS701_Final_Term_Solution - Part III CS701 Solved 25 MID Term Most important QA
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 )