In the state space tree of 0/1 knapsack problem solved using Branch and Bound strategy, identify the solution.

 Find the space complexity of the following code segment.

m=5;

int findSum(int a[],int b[], int n)

{

sum=m;

for(i=1; i<=n; i++)

              sum=b[i]+a[i];

return sum

}

 Spurious hit in Rabin Karp string matching algorithm is the case where the following is true.

In a network flow graph where “V” is a set of vertices, “s-t cut” is defined as

Compute the value of -25 mod 16.

  In the following network flow graph, the following values are given. It is aimed to find maximum flow from source to sink.

Augment flow along the augmenting path “source->A->sink”, what will be the change in capacity and flow values along the edges.

Match the time complexities of Naive, KMP and Rabin Karp string matching algorithms where ‘m’ is the length of the string and ‘n’ is the length of the text.

1.       Naive                          a. O(m+n)

2.       KMP                            b. O(n)

3.       Rabin Karp                c. O(mn)

 What is the output of the following recursive function when cal(2,3) is called?

int cal(int a, int b)

  The following is the state space tree of job sequencing problem. Identify to which type it belongs.

The redundant comparisons in naive string-matching algorithm are reduced in KMP string matching algorithm through the following.