### SET 6

Question 1

**A program P reads in 500 integers in the range [0..100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?**

A : An array of 50 numbers

B : An array of 100 numbers

C : An array of 500 numbers

D : A dynamically allocated array of 550 numbers

Answer Discuss it!

.

Correct answer is :A

Solution :

An array of size 50 looks the best option to store number of students for each score. We need to store frequencies of scores above 50. We can ignore scores below 50 and to index the scores above 50, we can subtract 50 from the score value

Question 2

**An undirected graph C has n nodes. Its adjacency matrix is given by an n × n square matrix whose**

(i) diagonal elements are 0's, and

(ii) non-diagonal elements are l's.

Which one of the following is TRUE?

A : Graph G has no minimum spanning tree (MST)

B : Graph G has a unique MST of cost n-1

C : Graph G has multiple distinct MSTs, each of cost n-1

D : Graph G has multiple spanning trees of different costs

Answer Discuss it!

.

Correct answer is :C

Solution :

If all non diagonal elements are 1, then every vertex is connected to every other vertex in the graph with an edge of weight 1. Such a graph has multiple distinct MSTs with cost n-1.

Question 3

**The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be**

A : O(n)

B : O(n logn)

C : O(n^{3/2})

D : O(n^{3})

Answer Discuss it!

.

Correct answer is :D

Solution :

In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. If the original relation is transitive, the transitive closure will be that same relation; otherwise, the transitive closure will be a different relation.

In computer science the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node othe

Question 4

**Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 Which one of the following is FALSE?**

A : T(n) = O(n^{2})

B : T(n) = θ(n log n)

C : T(n) = Ω(n^{2})

D : T(n) = O(n log n)

Answer Discuss it!

.

Correct answer is :C

Solution :

The given recurrence relation can be solved using Master Theorem. It lies in case 2 of Master Theorem. Or, if you remember recurrence relation of Merge Sort or best case Quick Sort, you can guess the value of T(n).

T(n) = θ(nLogn)

By definition of Big O notation, we can say.

θ(nLogn) = O(nLogn) = O(n^2)

θ(nLogn) ca be equal to Ω (n) or Ω (nLogn), but not Ω (n^2)

Question 5

**Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be implemented using the binary heap data structure with time complexity:**

A : O(| V |^{2})

B : O (| E | + | V | log | V |)

C : O (| V | log | V |)

D : O ((| E | + | V |) log | V |)

Answer Discuss it!

.

Correct answer is :D

Question 6

**Suppose there are ⌈ log n ⌉ sorted lists of ⌊ n/log n ⌋ elements each. The time complexity of producing a sorted list of all these elements is : (Hint : Use a heap data structure)**

A : O(n log log n)

B : θ (n log n)

C : Ω (n log n)

D : Ω (n3/2)

Answer Discuss it!

.

Correct answer is :A

Solution :

We can merge x arrays of each size y in in O(xy*Logy) time using Min Heap.

x = n/Logn y = Logn We get O(n/Logn * Logn * Log Log n) which is O(nLogLogn)

Question 7

**Let s and t be two vertices in a undirected graph G + (V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y The edge e must definitely belong to:**

A : the minimum weighted spanning tree of G

B : the weighted shortest path from s to t

C : each path from s to t

D : the weighted longest path from s to t

Answer Discuss it!

.

Correct answer is :A

Solution :

This is the idea used in Prim's algorithm. The minimum weight cut edge is always a minimum spanning tree edge.

Question 8

**Let s and t be two vertices in a undirected graph G + (V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum weight amongst all those edges that have one vertex in X and one vertex in Y.**

A : a path from s to t in the minimum weighted spanning tree

B : a weighted shortest path from s to t

C : an Euler walk from s to t

D : a Hamiltonian path from s to t

Answer Discuss it!

.

Correct answer is :B

Question 9

**We are given 9 tasks T1, T2.... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the dith unit of time.**

What is the maximum profit earned?

A : 147

B : 165

C : 167

D : 175

Answer Discuss it!

.

Correct answer is :A

Solution :

Task T1 T2 T3 T4 T5 T6 T7 T8 T9
Profit 15 20 30 18 18 10 23 16 25
Deadline 7 2 5 3 4 5 2 7 3

To maximize profit, we can finish tasks in following order T7, T2, T9, T5, T3, T8, T1. We get the maximum profit as 23 + 20 + 25 + 18 + 30 + 16 + 15 = 147

Question 10

**We are given 9 tasks T1, T2.... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the dith unit of time.Are all tasks completed in the schedule that gives maximum profit?**

A : All tasks are completed

B : T1 and T6 are left out

C : T1 and T8 are left out

D : T4 and T6 are left out

Answer Discuss it!

.

Correct answer is :D

Solution :

Task T1 T2 T3 T4 T5 T6 T7 T8 T9
Profit 15 20 30 18 18 10 23 16 25
Deadline 7 2 5 3 4 5 2 7 3

To maximize profit, we can finish tasks in following order T7, T2, T9, T5, T3, T8, T1

Question 11

**Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is 2|i-j|. The weight of a minimum spanning tree of G is:**

A : n-1

B : 2n-2

C : nC2

D : 2

Answer Discuss it!

.

Correct answer is :B

Solution :

Minimum spanning tree of such a graph is

v1
v2
v3
v4
.
.
.
vn

Weight of the minimum spanning tree

= 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2| n – (n-1) |

= 2n – 2

Question 12

**To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:**

A : Queue

B : Stack

C : Heap

D : B-Tree

Answer Discuss it!

.

Correct answer is :A

Solution :

The shortest path in an un-weighted graph means the smallest number of edges that must be traversed in order to reach the destination in the graph. This is the same problem as solving the weighted version where all the weights happen to be 1. If we use Queue (FIFO) instead of Priority Queue (Min Heap), we get the shortest path in linear time O(|V| + |E|). Basically we do BFS traversal of the graph to get the shortest paths.

Question 13

**Which one of the following in place sorting algorithms needs the minimum number of swaps?**

A : Quick sort

B : Insertion sort

C : Selection sort

D : Heap sort

Answer Discuss it!

.

Correct answer is :C

Solution :

For selection sort, number of swaps required is minimum ( O(n) ).

Question 14

**An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array.**

A : Solves it in linear time using a left to right pass of the array

B : Solves it in linear time using a right to left pass of the array

C : Solves it using divide and conquer in time θ(nlogn)

D : Solves it in time Theta(n^2)

Answer Discuss it!

.

Correct answer is :B

Solution :

Scan all the elements from right to left in array and keep track of maximum till now. When maximum changes it’s value, print it.

So it will take linear time.

Question 15

**Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?**

A : (a—b),(d—f),(b—f),(d—c),(d—e)

B : (a—b),(d—f),(d—c),(b—f),(d—e)

C : (d—f),(a—b),(d—c),(b—f),(d—e)

D : (d—f),(a—b),(b—f),(d—e),(d—c)

Answer Discuss it!

.

Correct answer is :D

Solution :

The edge (d-e) cannot be considered before (d-c) in Kruskal's minimum spanning tree algorithm because Kruskal’s algorithm picks the edge with minimum weight from the current set of edges at each step.

Question 16

**Let T be a depth first search tree in an undirected graph G. Vertices u and n are leaves of this tree T. The degrees of both u and n in G are at least 2. which one of the following statements is true?**

A : There must exist a vertex w adjacent to both u and n in G

B : There must exist a vertex w whose removal disconnects u and n in G

C : There must exist a cycle in G containing u and n

D : There must exist a cycle in G containing u and all its neighbours in G.

Answer Discuss it!

.

Correct answer is :B

Solution :

Since they are leaves in DFS, they must be separable by a vertex.

Question 17

**An implementation of a queue Q, using two stacks S1 and S2, is given below:**

void insert(Q, x)

{

push (S1, x);

}

void delete(Q){

if(stack-empty(S2)) then

if(stack-empty(S1)) then {

print(“Q is empty”);

return;

}

else while (!(stack-empty(S1))){

x=pop(S1);

push(S2,x);

}

x=pop(S2);

}

Let n insert and m (<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?

A : n+m <= x < 2n and 2m <= y <= n+m

B : n+m <= x < 2n and 2m<= y <= 2n

C : 2m <= x < 2n and 2m <= y <= n+m

D : 2m <= x <2n and 2m <= y <= 2n

Answer Discuss it!

.

Correct answer is :A

Solution :

The order in which insert and delete operations are performed matters here.
The best case: Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push operations are performed. So, total m+ n push (n push for insert() and m push for delete()) operations and 2m pop operations are performed.

The worst case: First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations and n push operation are performed

Question 18

**A set X can be represented by an array x[n] as below in the image:
**

Consider the following algorithm in which x,y and z are Boolean arrays of size n:

algorithm zzz(x[] , y[], z [])
{
int i;
for (i=O; i<n; ++i)
z[i] = (x[i] ^ ~y[i]) V (~x[i] ^ y[i])
}

The set Z computed by the algorithm is:

A : (X ∪ Y)

B : (X ∩ Y)

C : (X-Y) ∩ (Y-X)

D : (X-Y) ∪ (Y-X)

Answer Discuss it!

.

Correct answer is :A

Solution :

The expression x[i] ^ ¬ y[i]) results the only 1s in x where corresponding entry in y is 1.
The expression ¬ x[i] ^ y[i]) results the only 1s in y where corresponding entry in x is 1.

Question 19

**Consider the following recurrence: Which one of the following is true?**

T(n) = 2T( ⌈√n ⌉) + 1, T(1) = 1

A : T(n) = θ(loglogn)

B : T(n) = θ(logn)

C : T(n) = θ(√n)

D : T(n) = θ(n)

Answer Discuss it!

.

Correct answer is :B

Solution :

This question can be solved by first change of variable and then Master Method.

Let n = 2^m

T(2^m) = T(2^(m/2)) + 1

Let T(2^m) = S(m)

S(m) = 2S(m/2) + 1

Above expression is a binary tree traversal recursion whose time complexity is (m). You can also prove using Master theorem.

S(m) = (m)

= (logn) /* Since n = 2^m */

Now, let us go back to the original recursive function T(n)

T(n) = T(2^m) = S(m)

=

Question 20

**Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.**

A : O(n^{2} Logn)

B : O(n^{2} )

C : O(n Logn Logn)

D : O(n Logn)

Answer Discuss it!

.

Correct answer is :D

Solution :

If we use median as a pivot element, then the recurrence for all cases becomes

T(n) = 2T(n/2) + O(n)

The above recurrence can be solved using Master Method. It falls in case 2 of master method.

Question 21

**Given two arrays of numbers a1, a2, a3,...an and b1, b2, .. bn where each number is 0 or 1, the fastest algorithm to find the largest span(i, j) such that ai + ai+1, ....aj = bi, bi+1, .. bj. or report that there is not such span,**

A : Takes O(n^{3}) and Ω (2^{n}) time if hashing is permitted

B : Takes O(n^{3}) and Ω (n^{2.5}) time in the key comparison model

C : Takes θ(n) time and space

D : Takes O(√ n) time only if the sum of the 2n elements is an even number

Answer Discuss it!

.

Correct answer is :C

Question 1

.

Correct answer is :A

Solution :

An array of size 50 looks the best option to store number of students for each score. We need to store frequencies of scores above 50. We can ignore scores below 50 and to index the scores above 50, we can subtract 50 from the score value

Question 2

(i) diagonal elements are 0's, and

(ii) non-diagonal elements are l's.

Which one of the following is TRUE?

.

Correct answer is :C

Solution :

If all non diagonal elements are 1, then every vertex is connected to every other vertex in the graph with an edge of weight 1. Such a graph has multiple distinct MSTs with cost n-1.

Question 3

.

Correct answer is :D

Solution :

In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. If the original relation is transitive, the transitive closure will be that same relation; otherwise, the transitive closure will be a different relation.

In computer science the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node othe

Question 4

.

Correct answer is :C

Solution :

The given recurrence relation can be solved using Master Theorem. It lies in case 2 of Master Theorem. Or, if you remember recurrence relation of Merge Sort or best case Quick Sort, you can guess the value of T(n).

T(n) = θ(nLogn)

By definition of Big O notation, we can say.

θ(nLogn) = O(nLogn) = O(n^2)

θ(nLogn) ca be equal to Ω (n) or Ω (nLogn), but not Ω (n^2)

Question 5

.

Correct answer is :D

Question 6

.

Correct answer is :A

Solution :

We can merge x arrays of each size y in in O(xy*Logy) time using Min Heap.

x = n/Logn y = Logn We get O(n/Logn * Logn * Log Log n) which is O(nLogLogn)

Question 7

.

Correct answer is :A

Solution :

This is the idea used in Prim's algorithm. The minimum weight cut edge is always a minimum spanning tree edge.

Question 8

.

Correct answer is :B

Question 9

What is the maximum profit earned?

.

Correct answer is :A

Solution :

Task T1 T2 T3 T4 T5 T6 T7 T8 T9 Profit 15 20 30 18 18 10 23 16 25 Deadline 7 2 5 3 4 5 2 7 3

To maximize profit, we can finish tasks in following order T7, T2, T9, T5, T3, T8, T1. We get the maximum profit as 23 + 20 + 25 + 18 + 30 + 16 + 15 = 147

Question 10

.

Correct answer is :D

Solution :

Task T1 T2 T3 T4 T5 T6 T7 T8 T9 Profit 15 20 30 18 18 10 23 16 25 Deadline 7 2 5 3 4 5 2 7 3

To maximize profit, we can finish tasks in following order T7, T2, T9, T5, T3, T8, T1

Question 11

.

Correct answer is :B

Solution :

Minimum spanning tree of such a graph is

v1 v2 v3 v4 . . . vn

Weight of the minimum spanning tree

= 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2| n – (n-1) |

= 2n – 2

Question 12

.

Correct answer is :A

Solution :

The shortest path in an un-weighted graph means the smallest number of edges that must be traversed in order to reach the destination in the graph. This is the same problem as solving the weighted version where all the weights happen to be 1. If we use Queue (FIFO) instead of Priority Queue (Min Heap), we get the shortest path in linear time O(|V| + |E|). Basically we do BFS traversal of the graph to get the shortest paths.

Question 13

.

Correct answer is :C

Solution :

For selection sort, number of swaps required is minimum ( O(n) ).

Question 14

.

Correct answer is :B

Solution :

Scan all the elements from right to left in array and keep track of maximum till now. When maximum changes it’s value, print it.

So it will take linear time.

Question 15

.

Correct answer is :D

Solution :

The edge (d-e) cannot be considered before (d-c) in Kruskal's minimum spanning tree algorithm because Kruskal’s algorithm picks the edge with minimum weight from the current set of edges at each step.

Question 16

.

Correct answer is :B

Solution :

Since they are leaves in DFS, they must be separable by a vertex.

Question 17

void insert(Q, x)

{

push (S1, x);

}

void delete(Q){

if(stack-empty(S2)) then

if(stack-empty(S1)) then {

print(“Q is empty”);

return;

}

else while (!(stack-empty(S1))){

x=pop(S1);

push(S2,x);

}

x=pop(S2);

}

Let n insert and m (<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?

.

Correct answer is :A

Solution :

The order in which insert and delete operations are performed matters here. The best case: Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push operations are performed. So, total m+ n push (n push for insert() and m push for delete()) operations and 2m pop operations are performed.

The worst case: First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations and n push operation are performed

Question 18

Consider the following algorithm in which x,y and z are Boolean arrays of size n:

algorithm zzz(x[] , y[], z []) { int i; for (i=O; i<n; ++i) z[i] = (x[i] ^ ~y[i]) V (~x[i] ^ y[i]) }

The set Z computed by the algorithm is:

.

Correct answer is :A

Solution :

The expression x[i] ^ ¬ y[i]) results the only 1s in x where corresponding entry in y is 1. The expression ¬ x[i] ^ y[i]) results the only 1s in y where corresponding entry in x is 1.

Question 19

T(n) = 2T( ⌈√n ⌉) + 1, T(1) = 1

.

Correct answer is :B

Solution :

This question can be solved by first change of variable and then Master Method.

Let n = 2^m

T(2^m) = T(2^(m/2)) + 1

Let T(2^m) = S(m)

S(m) = 2S(m/2) + 1

Above expression is a binary tree traversal recursion whose time complexity is (m). You can also prove using Master theorem.

S(m) = (m)

= (logn) /* Since n = 2^m */

Now, let us go back to the original recursive function T(n)

T(n) = T(2^m) = S(m)

=

Question 20

.

Correct answer is :D

Solution :

If we use median as a pivot element, then the recurrence for all cases becomes

T(n) = 2T(n/2) + O(n)

The above recurrence can be solved using Master Method. It falls in case 2 of master method.

Question 21

.

Correct answer is :C