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