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

}

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

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

  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.

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

Compute the value of -25 mod 16.

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

int cal(int a, int b)

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)

  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.