CS-701 Theory of Computation
Mcqs
Q & A
Video
Online Test
Foram
Course Category: Computer Science/Information Technology
Course Level: Graduate
Credit Hours: 3
Pre-requisites: CS402, MTH202
Share this page on:
Downloads:
CS701 Handouts version 1
CS701_sipser_chapter8_solution
CS701_Final_Term_2015_Mega_File
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
Books

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

Solution ( Introduction to the Theory of Computation )