
Course Category: 
Computer Science/Information Technology 
Course Level: 
Graduate 
Credit Hours: 
3 
Prerequisites: 
CS402 MTH202 

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 Contents
Introduction, Set Thoery, Sequences, Tuples, Functions, Relations, Graphs, Turing Machines, Enumerators, Dovetailing, The ChurchTuring 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, NonDeterministic Time, The Class P, The Class NP, Polynomial Time Verifiers, Subset Sum Problem, Satisfiability, NPCompletness, 3Color Problem, The CookLevin 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, PSPACECompleteness, TQBF, Prove that TQBF is PSPACEComplete, FORMULAGAME, Generalized Geography, LOGSPACE Transducer, Prove the Theorem: NL = coNL.
Course Related Links
Useful link for course related material, taught by Leonid A. Levin at Boston University
Course Related valuable link provided at Brown University
Useful link for course related material, provided by John McCarthy at Stanford University
Course Related valuable link provided by Virginia Tech University
Research Topics and Good Course Related Material provided by MIT, USA
Course Related valuable link provided by University of California, Berkeley (UCB)
Good Material provided by Princeton University
Research Topics and Good Course Related Material provided by Harvard University
Useful link for course related material, taught by David Matuszek at University of Pennsylvania 


