We have been working very hard since 2009 to facilitate in your learning Read More. We can't keep up without your support. Donate Now.

www.vustudents.ning.com

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + Link For Past Papers, Solved MCQs, Short Notes & More

# CS701 Theory of Computation Course Page - CS701 COURSE SYNOPSIS - CS701 COURSE LEARNING OUTCOMES - CS701 COURSE CONTENTS

CS701 Theory of Computation Course Page - CS701 COURSE SYNOPSIS - CS701 COURSE LEARNING OUTCOMES - CS701 COURSE CONTENTS

 Course Category: Computer Science/Information Technology Course Level: Graduate Credit Hours: 3 Pre-requisites:

# 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 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.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

Views: 15

## Latest Activity

11 minutes ago
12 minutes ago
40 minutes ago
41 minutes ago
1 hour ago
Muhammad Azeem joined +M.Tariq Malik's group

### FIN625 Credit & Risk Management

1 hour ago
1 hour ago
Muhammad Azeem joined +M.Tariq Malik's group

### FIN624 Islamic Mode of Financing

1 hour ago
Kamboh (Graphic Designer) updated their profile
1 hour ago
Muhammad Azeem joined +M.Tariq Malik's group

### BNK603 Consumer Banking

1 hour ago
Aleeha joined +M.Tariq Malik's group

### CS304 Object Oriented Programming

2 hours ago
Kamboh (Graphic Designer) posted a discussion

2 hours ago

1

2

3