VU

Search Here All Mid & Final Papers

CS701 Current FinalTerm Paper 20 February 2018 | FALL 2017 |

CS701 Current FinalTerm Paper 20 February 2018 | FALL 2017 |

CS701 Current FinalTerm Paper 20 February 2018 | FALL 2017 |

CS701 Paper 20-02-2018

Q1: Let ALBA = {<M,w> | M is an LBA (Linear Bounded Automaton) that accepts input w}. Show that ALBA is PSPACE-complete.

Q2: Show that if P=NP ,then every language A belong to P, except A= and A= * is NP-Complete.

Q3: For a CNF-formula with m variable and c clauses that you can construction polynomial time an NFA with O(cm) states that accepts all non-satisfying assignments, represented as Boolean strings of length m
Q4: A directed Graph is STRONGLY-CONNECTED of every two nodes are connected by a directed graph in each direction. Let STRONGLY-CONNECTED = {<G>|G is strongly connected graph}. Show that STRONGLY-CONNECTED is NP-Complete.


Cs701 My Paper Today 10.30AM

Question 1
Let A be the language of properly nested parentheses. For example, (()) and (()(()))() are in A, but )( is not. Show that A is in L. 

Question 2
Consider the following generalized geography game wherein the start node is the one with the arrow pointing in form nowhere. Does Player I have a winning strategy? Does Player II? Give reasons for your answers.

CS701:20-02-2018:Tuesday:4:30PM

Q:1: Let ALBA = {<M,w> | M is an LBA (Linear Bounded Automaton) that
accepts input w}. Show that ALBA is PSPACE-complete?

Q2: The game of Nim is played with a collection of piles of sticks. In one move a
player may remove any nonzero number of sticks from a single pile. The players
alternately take turns making moves. The player who removes the very last stick
loses. Say that we have a game position in Nim with k piles containing s1, ..., sk
sticks. Call the position balanced if, when each of the numbers si is written in binary
and the binary numbers are written as rows of a matrix aligned at the low order
bits, each column of bits contains an even number of 1s. Prove the following two
facts.
(a):Starting in an unbalanced position, a single move exists that changes the
position into a balanced one.
(b):Starting in a balanced position, every single move changes the position into anunbalanced one.


Q.3: Let G represents an undirected graph. Let LPATH={<G,a,b,k>|G contains a simple path of length at most k from a to b}
Show that LPATH is NP-Complete. You may assume that NP-Completeness of
UHAMPATH, the Hamiltonian path problem for undirected graph?


Q.4: Related to NAT-SAT? (Note:Sorry! I have no idea about it)

Welcome to Our Site! - Virtual Ustaad This site is basically Design to help all Virtual University Students in their Study programs.its a plateform where you can get all your past papers which are made by Different Students of Virtual University. The Main purpose of this site to help and guide you by giving all materials, which will be helpful for you.