+971 55 359 3828 vuassassins@gmail.com
Spread the love

CS701 Theory of Computation1

In CS701 Theory of Computation we have you covered with Digitized Past Papers From Fall of Mid Term and Final Term.

NOTE: Click on Preparation Tab to take the MCQ’s Tests.

CS701 Final- Term Paper                                                             View     Download
CS701_Final_Term_2015_Mega_File                                          View     Download
CS701-Completely-Solved-Mid-Term-Exam-Papers                     View     Download

1 Comment


    Show that A is NP-Complete.
    2. Prove that Double SAT is NP-Complete (by reducing from 3 SAT)
    3. Prove that SET SPLITTING is NP-Complete.
    4. Prove Multi SAT is NP-Complete.
    5. Show that directed hymoltonian cycle is NP-Complete.
    6. Show that half clique is NP-Complete.
    7. Let CNF-k = { | ɸ is satisfiable CNF-formula where each variable appears in at most k
    places}. Show that CNF3 is NP-Complete.
    8. A subset of nodes of a graph is a dominating set if every other node of G is adjacent to
    some node in the subset. Let DOMINATING-SET={ | G has a dominating set with k
    nodes}. Show that it is NP-Complete by giving a reduction from VERTEX-COVER.
    9. Let TRUE-SAT; given Boolean expression E that is true when all the variables are made
    true, is there some other truth assignment besides all true that make E true. Show that
    TURE-SAT is NP-Complete by reducing SAT to it.
    10. Let NEAR TAUT; given Boolean expression E all the variables are made f, is there some
    other truth assignment besides all f that make E true. Show that NEAR TAUT is NPComplete by reducing SAT to it.
    11. Let NEAR-TAUT: E is a Boolean expression having when at most one true makes it false.
    Show that complement of NEAT-TAUT is in NP-Complete using reduction it to SAT.
    12. Let G represent and undirected graph. Also let LPATH = {|G contains a simple
    path of length k for a to b>}. Show that LPATH is NP complete. You may assume that NP
    completeness of UHAMPTH the HAMPATH problem of undirected graph.
    13. A directed Graph is STRONGLY-CONNECTED of every two nodes are connected by a
    directed graph in each direction. Let STRONGLY-CONNECTED = {|G is strongly
    connected graph}. Show that STRONGLY-CONNECTED is NP-Complete.
    14. Let A = {|NTM, M accepts input x within t steps on at least one branch}. Show
    that A is NP-Complete.
    15. Prove cycle- length problem is NL-Complete.
    16. Let ADD = { | x, y, z >0 are binary integers and x + y =z}.
    Show that ADD ϵ LSPACE.
    17. Let PAL-ADD = { | x, y >0 are binary integers where x + y is an integer whose
    binary representation is palindrome}. Show that PAL-ADD ϵ LSPACE.
    18. Nim game question to prove unbalance and balance
    19. See the Questions of Sipser Book 2013 edition 3
    Exercises: 7.17, 7.22, 7.28, 7.30, 8.13, 8.19, 8.22, 8.22b, 8.27
    20. Winning strategy (q 8.3 )