Define PSPACE and NPSPACE, What can you say about the

८.
relationship 2 between PSPACE and NPSPACE?

a. Assumes a flow network G = (V, E Each edge capacity

c(u,v) is nonnegative. 3
The source is denoted by s and the sink by t. The
value of a flow is denoted by I 7 1
State whether the following statement is TRUE or FALSE.
Explain your answer.

b. Compute eS Rea function for the pattern abcaabbccab
when the 4lp. 318 ए = 18, b, cl.

c. Consider the following algorithm to determine whether
or not an undirected 3 graph has a clique of size k.
First, generate all subsets of the vertices containing
exactly k vertices. Next, check whether any of the
subgraphs induced by these subsets is complete (i.e.
forms a clique).

Why is this not a polynomial-time algorithm for the
clique problem, thereby implying that P = NP?
PART C
a. QuickSelect is the following simple randomized algorithm

for finding the kth 6 smallest element in an unsorted set S.

QuickSelect(S, k):

I. Pick a pivot element p uniformly at random from S.

2. By comparing p to each element of S, split S into
two sets: