Moaaz / Moazz
Browse Moaaz's dedicated papers or search the alternate spelling.
Past Papers & Contributor Collections
Choose an exam term or contributor to browse the available Virtual University papers. Each collection is listed separately so you can go directly to the material you need.
Midterm Papers
Finalterm Papers
Contributor Collections
Arslan
Arslan's papers are kept separate from other contributors.
Tariq
Tariq's papers are kept in their own collection.
Waqar Siddhu
Browse posts and solved files associated with Waqar Siddhu.
Midterm & Finalterm, Subject by Subject
More Study Papers
CS701 Current FinalTerm Paper 20 February 2018 | FALL 2017 |
🤖
Ustaad Bot: Is file ko download karo, MCQs practice karo — A+ pakka! 🎯
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)