theITeducaion.com will provide you all material related to CS701 theory of computation course including, overview, contents, books and handouts, cs701 solution manual, cs701 midterm final term solved passed papers, assignments related videos etc. Bookmark this page if you are student of this course.
Course overview-CS701
This course is a compulsory course of MSCS study scheme. HEC has declared it a core subject. It is about the applied mathematical concepts like Turing Machine and other models in Computer science core discipline. Many students consider it very tough for their MSCS study scheme. I agree that this is tough in one sense that most of the students don’t care about its pre-requisite courses while in their undergraduate study. Theory of automata, compiler construction and machine learning are the pre-requisite courses. It has been studied throughout the world at MS and M.Phil level. In Virtual university of Pakistan this course is taught by our respected teacher Dr. Sarmad Abbassi (PhD from USA in computer sciences). He is the best teacher of theory of computation in Pakistan.
CS701 Course contents for VU-MSCS
For Details visit ocw.vu.edu.pk | 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. | 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. | ||||||
| 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. | ||||||||
| 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. | ||||||||
Recommended books
- Introduction to the Theory of Computation Textbook by Michael Sipser (Download Book
CS701 Passing strategy (Mid Term / final Term)
Book chapter 3, 4, 5, 6, 7 are the part of the syllabus. Learn its all examples, and exercises by heart even without any concept.
cs701 Mid-Term / Final-Term Good marks strategy
Listen All CS701 videos lectures from YouTube or get its videos from campus. Prepare all slides handouts and master the skills of writing formal description of turning machine. Learn how to prove different theorms of time and space complexity. Above stated chapters are in the course. Make sure all chapters are learnt by heart with its all solutions of exercises. Solution manual of theory of computation book by Sir Michael Sisper can be download from our group.
Term/Academic paper rules and regulations
No term/academic papers is for this course as per new study scheme announced by VU. It may change time to time. Although a research presentation of 5% weight-age will be announced after mid term exam on announced topics.
CS701 Topics for Academic papers / presentation
wikipedia has listed more than 50 best and important topics in which research paper or presentation can be made.
CS701 Handouts
Virtual university provide best reading and allied material for all its courses. You may download all related material for CS701 from your LMS under download section. Secondly you may visit VU Content Library website to download realted and allied CS701 materials. Here are direct links
Download CS701 handouts, slides and other related materials
If links do not work then login to vu content library with your username and password and search for CS701 course and download directly. You may use “guest” username and password also.
How to get Help
- Danishkada.net is the only institution in Pakistan who provide 100% free online coaching for Virtual university of Pakistan courses including CS701. Join it and learn all subjects in online classes scheduled form 8pm to 11pm daily.
- Join Facebook group theITeducation to get free help on solving CS701 assignments mid-term videos and final term videos for preparation and academic paper training and paid tution
CS701 Past assignments and papers
- Marked Handouts with past papers questions Fall 2017
- Latest past papers from FB group MSCS (might need FB login)
Note: Please share this page if you find it helpful. Keep visiting theITeducation.com for assignment and academic paper help ideas and paid online tuition of MSCS subjects. A lot of help material is shared 100% free on FB group. Join https://www.facebook.com/groups/theiteducation/
