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.
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
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)
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)
Emoticon