### SET 2

Question 1

**Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?**

A : G_{1} = (V,E_{1}) where E_{1} = { (u,v) | (u,v) ∉ E }

B : G_{2} = (V,E_{2}) where E_{2} = { (u,v) | (v,u) ∈ E }

C : G_{3} = (V,E_{3}) where E_{1} = { (u,v) | there is a path of length <=2 from

D : G_{4} = (V_{4},E) where V_{4} is the set of vertices in G which are not isol

Answer Discuss it!

.

Correct answer is :B

Question 2

**Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?**

A : θ (n)

B : θ (n+m)

C : θ (n^{2})

D : θ (m^{2})

Answer Discuss it!

.

Correct answer is :C

Solution :

DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V ) time, so overall the running time will be O(V^{2})

Question 3

**Consider the directed graph given below. **

Which one of the following is TRUE?

Note: Edge is from R to Q

A : The graph does not have any topological ordering

B : Both PQRS and SRQP are topological orderings

C : Both PSRQ and SPRQ are topological orderings.

D : PSRQ is the only topological ordering.

Answer Discuss it!

.

Correct answer is :C

Solution :

Topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. Topological ordering is possible iff graph has no directed cycles.

(A) As the given graph doesn’t contain any directed cycles, it has at least one topological ordering. So option (A) is false

(B) PQRS cannot be topological ordering because S should come before R in the ordering as there is a directed edge from S to R and Q

Question 4

**Let P be a quick sort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?**

A : t1=5

B : t1 < t2

C : t1 > t2

D : t1 = t2

Answer Discuss it!

.

Correct answer is :C

Solution :

Partition algorithm for quick sort

Partition (A,P,q) //A [P,.....]

x <- A [P[ // pivot A= [P]

i <-P

for j= P + 1 to q

do if A [j] <= x

then i <- i + 1

exchange A [i] <-> A [j]

exchange A [P] <-> A [i]

return i [returning where pivot element is there after partitioning]

Recursively call the above algorithm for the two sub arrays [elements before and after pivot element] to complete the sorting.

Question 5

**The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.**

Answer Discuss it!

.

Correct answer is :148

Solution :

To find minimum and maximum element out of n numbers, we need to have at least (3n/2-2) comparisons.

Question 6

**Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are**

A : 3,0 and 1

B : 3,3 and 3

C : 4,0 and 1

D : 3,0 and 2

Answer Discuss it!

.

Correct answer is :A

Solution :

Maximum&minimum chain lengths are 3&0 respectively

Average chain length = 0+3+1+1+0+1+2+0+1/9 = 1

Question 7

**Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {i, f): 1 <= i <= 12, 1 <= j <= 12}. There is an edge between (a,b) and (c,d) if |a - c| <= 1 and |b - d| <= 1 The number of edges in the graph is _____________.**

Answer Discuss it!

.

Correct answer is :506

Solution :

The graph formed by the description contains 4 vertices of degree 3 and 40verices of degree 5 and 100 vertices of degree 8.

According to sum of the degrees theorem 4*3+40*5+100*8 = 2|E|

|E| = 1012/2 = 506

Question 8

**Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? **

T(n) = | 2T(n/2) + log n

A : θ (n)

B : θ (nlog n)

C : θ (n^{2})

D : θ (log n)

Answer Discuss it!

.

Correct answer is :A

Question 9

**Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing **

A : the shortest path between every pair of vertices.

B : the shortest path from W to every vertex in the graph.

C : the shortest paths from W to only those nodes that are leaves of T.

D : the longest path in the graph.

Answer Discuss it!

.

Correct answer is :B

Solution :

One of the application of BFS algorithm is to find the shortest path between nodes u and v. But in the given question the BFS algorithm starts from the source vertex w and we can find the shortest path from w to every vertex of the graph

Question 10

**Consider two strings A "= q pqrr " and B = "pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.**

Answer Discuss it!

.

Correct answer is :34

Solution :

Given is

A = “qpqrr”

B = “pqprqrp”

The longest common subsequence (not necessarily contiguous) between A and B is having 4 as the length, so x=4 and such common subsequences are as follows:

(1) qpqr

(2) pqrr

(3) qprr

So y = 3 (the number of longest common subsequences) hence x+10y = 4+10*3 = 34.

Question 11

**The number of distinct minimum spanning trees for the weighted graph below is**

Answer Discuss it!

.

Correct answer is :6

Question 12

**Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.**

Answer Discuss it!

.

Correct answer is :19

Question 13

**You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is**

A : O(n^{2})

B : O(n logn)

C : θ(n logn)

D : O(n^{3})

Answer Discuss it!

.

Correct answer is :A

Solution :

The Worst case time complexity of quick sort is O (n^{2}).
The central element is chosen as the pivot and not the median so that central element could be an extreme in the final array every time.

Question 14

**Which of the following statements are CORRECT?**

1)Static allocation of all data areas by a compiler makes it impossible to implement recursion.

2)Automatic garbage collection is essential to implement recursion.

3)Dynamic allocation of activation records is essential to implement recursion.

4)Both heap and stack are essential to implement recursion.

A : 1 and 2 only

B : 2 and 3 only

C : 3 and 4 only

D : 1 and 3 only

Answer Discuss it!

.

Correct answer is :D

Solution :

To implement recursion, activation record should be implemented by providing dynamic memory allocation. This dynamic allocation is done from runtime stack. Heap is essential to allocate memory for data structures at run-time, not for recursion.

So statement 1 and 3 are correct.

Question 15

**Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i, j with i < j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y), T(z)). Then the value of the product yz is _____.
**

Answer Discuss it!

.

Correct answer is :150

Solution :

By definition, T(9) = Dist. From 9 to 100

As given, T(9) = 1+min (T(y), T()z) = 1+min (Dist. from y to 100, Dist. From z to 100)

1=Dist. from 9 to y/Dist. From 9 to z

There are only two such values-one is the simple one step on number line i.e. 10, and the other is the shortcut associated with 9 i.e. 15.

Therefore, y and z are 10 and 15 (in any order)

Product yz = 150. Answ

Question 16

**Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O( n**^{a} log^{b} n + m^{c} log^{d} n , the value of a + 10b + 100c + 1000d is _______.

Answer Discuss it!

.

Correct answer is :110

Solution :

It takes (log n ) time to determine numbers n1 and n2 in balanced binary search tree T such that

1. n1 is the smallest number greater than or equal to L and there is no predecessor n’1 of n1 such that n’1 is equal to n1.

2. n2 is the largest number less than or equal to H and there is no successor of n’2 of n2 such that is equal to n2.

Since there are m elements between n1 and n2, it takes ‘m’ time to add all elements between n1 and n2.

So time complexity is O (log n + m)

Question 17

**Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?**

A : (97 × 97 × 97)/100^{3}

B : (99 × 98 × 97)/100^{3}

C : (97 × 96 × 95)/100^{3}

D : (97 × 96 × 95)/(3! × 100^{3})

Answer Discuss it!

.

Correct answer is :A

Question 18

**Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order. **

int ProcessArray (int * listA, int x, int n)

{

Int 1, j, k;

i = 0;

j = n – 1;

do { k = (i + j) /2;

if (x < = listA [k]) j = k – 1;

If (listA [k] < = x) i = k+1;

}

while (1 < = j);

If (listA [k] = = x)

return (k) ;

else return -1;

}

Which one of the following statements about the function ProcessArray is CORRECT?

A : It will run into an infinite loop when x is not in listA.

B : It is an implementation of binary search

C : It will always find the maximum element in listA.

D : It will return – 1 even when x is present in listA.

Answer Discuss it!

.

Correct answer is :B

Solution :

By the logic of the algorithm it is clear that it is an attempted implementation of Binary Search. So option C is clearly eliminated. Let us now check for options A and D.

A good way to do this is to create small dummy examples (arrays) and implement the algorithm as it is. One may make any array of choice. Running iterations of the algorithm would indicate that the loop exits when the x is not present. So option A is wrong. Also, when x is present, the correct index is indeed returned. D is

Question 1

.

Correct answer is :B

Question 2

.

Correct answer is :C

Solution :

DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V ) time, so overall the running time will be O(V

^{2})

Question 3

Which one of the following is TRUE?

Note: Edge is from R to Q

.

Correct answer is :C

Solution :

Topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. Topological ordering is possible iff graph has no directed cycles.

(A) As the given graph doesn’t contain any directed cycles, it has at least one topological ordering. So option (A) is false

(B) PQRS cannot be topological ordering because S should come before R in the ordering as there is a directed edge from S to R and Q

Question 4

.

Correct answer is :C

Solution :

Partition algorithm for quick sort

Partition (A,P,q) //A [P,.....]

x <- A [P[ // pivot A= [P]

i <-P

for j= P + 1 to q

do if A [j] <= x

then i <- i + 1

exchange A [i] <-> A [j]

exchange A [P] <-> A [i]

return i [returning where pivot element is there after partitioning]

Recursively call the above algorithm for the two sub arrays [elements before and after pivot element] to complete the sorting.

Question 5

.

Correct answer is :148

Solution :

To find minimum and maximum element out of n numbers, we need to have at least (3n/2-2) comparisons.

Question 6

.

Correct answer is :A

Solution :

Maximum&minimum chain lengths are 3&0 respectively

Average chain length = 0+3+1+1+0+1+2+0+1/9 = 1

Question 7

.

Correct answer is :506

Solution :

The graph formed by the description contains 4 vertices of degree 3 and 40verices of degree 5 and 100 vertices of degree 8.

According to sum of the degrees theorem 4*3+40*5+100*8 = 2|E|

|E| = 1012/2 = 506

Question 8

T(n) = | 2T(n/2) + log n

.

Correct answer is :A

Question 9

.

Correct answer is :B

Solution :

One of the application of BFS algorithm is to find the shortest path between nodes u and v. But in the given question the BFS algorithm starts from the source vertex w and we can find the shortest path from w to every vertex of the graph

Question 10

.

Correct answer is :34

Solution :

Given is

A = “qpqrr”

B = “pqprqrp”

The longest common subsequence (not necessarily contiguous) between A and B is having 4 as the length, so x=4 and such common subsequences are as follows:

(1) qpqr

(2) pqrr

(3) qprr

So y = 3 (the number of longest common subsequences) hence x+10y = 4+10*3 = 34.

Question 11

.

Correct answer is :6

Question 12

.

Correct answer is :19

Question 13

.

Correct answer is :A

Solution :

The Worst case time complexity of quick sort is O (n

^{2}). The central element is chosen as the pivot and not the median so that central element could be an extreme in the final array every time.

Question 14

1)Static allocation of all data areas by a compiler makes it impossible to implement recursion.

2)Automatic garbage collection is essential to implement recursion.

3)Dynamic allocation of activation records is essential to implement recursion.

4)Both heap and stack are essential to implement recursion.

.

Correct answer is :D

Solution :

To implement recursion, activation record should be implemented by providing dynamic memory allocation. This dynamic allocation is done from runtime stack. Heap is essential to allocate memory for data structures at run-time, not for recursion.

So statement 1 and 3 are correct.

Question 15

.

Correct answer is :150

Solution :

By definition, T(9) = Dist. From 9 to 100

As given, T(9) = 1+min (T(y), T()z) = 1+min (Dist. from y to 100, Dist. From z to 100)

1=Dist. from 9 to y/Dist. From 9 to z

There are only two such values-one is the simple one step on number line i.e. 10, and the other is the shortcut associated with 9 i.e. 15.

Therefore, y and z are 10 and 15 (in any order)

Product yz = 150. Answ

Question 16

^{a}log

^{b}n + m

^{c}log

^{d}n , the value of a + 10b + 100c + 1000d is _______.

.

Correct answer is :110

Solution :

It takes (log n ) time to determine numbers n1 and n2 in balanced binary search tree T such that

1. n1 is the smallest number greater than or equal to L and there is no predecessor n’1 of n1 such that n’1 is equal to n1.

2. n2 is the largest number less than or equal to H and there is no successor of n’2 of n2 such that is equal to n2.

Since there are m elements between n1 and n2, it takes ‘m’ time to add all elements between n1 and n2.

So time complexity is O (log n + m)

Question 17

.

Correct answer is :A

Question 18

int ProcessArray (int * listA, int x, int n)

{

Int 1, j, k;

i = 0;

j = n – 1;

do { k = (i + j) /2;

if (x < = listA [k]) j = k – 1;

If (listA [k] < = x) i = k+1;

}

while (1 < = j);

If (listA [k] = = x)

return (k) ;

else return -1;

}

Which one of the following statements about the function ProcessArray is CORRECT?

.

Correct answer is :B

Solution :

By the logic of the algorithm it is clear that it is an attempted implementation of Binary Search. So option C is clearly eliminated. Let us now check for options A and D.

A good way to do this is to create small dummy examples (arrays) and implement the algorithm as it is. One may make any array of choice. Running iterations of the algorithm would indicate that the loop exits when the x is not present. So option A is wrong. Also, when x is present, the correct index is indeed returned. D is