### SET 5

Question 1

**Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering? **

A : 1 2 3 4 5 6

B : 1 3 2 4 5 6

C : 1 3 2 4 6 5

D : 3 2 4 1 6 5

Answer Discuss it!

.

Correct answer is :D

Solution :

1 appears after 2 and 3 which is not possible in Topological Sorting.

Question 2

**Which of the following sorting algorithms has the lowest worst-case complexity?**

A : Merge sort

B : Bubble sort

C : Quick sort

D : Selection sort

Answer Discuss it!

.

Correct answer is :A

Solution :

Worst case complexities for the above sorting algorithms are as follows:

Merge Sort - nLogn

Bubble Sort - n^2

Quick Sort - n^2

Selection Sort - n^2

Question 3

**Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.**

A : 8, _, _, _, _, _, 10

B : 1, 8, 10, _, _, _, 3

C : 1, _, _, _, _, _,3

D : 1, 10, 8, _, _, _, 3

Answer Discuss it!

.

Correct answer is :B

Solution :

Let us put values 1, 3, 8, 10 in the hash of size 7.

Initially, hash table is empty

- - - - - - -

0 1 2 3 4 5 6

The value of function (3x + 4)mod 7 for 1 is 0, so let us put the value at 0

1 - - - - - -

0 1 2 3 4 5 6

The value of function (3x + 4)mod 7 for 3 is 6, so let us put the value at 6

1 - - - - - 3

0 1 2 3 4 5 6

The value o

Question 4

**In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by**

A : Dijkstra’s algorithm starting from S

B : Warshall’s algorithm

C : Performing a DFS starting from S

D : Performing a BFS starting from S

Answer Discuss it!

.

Correct answer is :D

Solution :

* Time Comlexity of the Dijkstra’s algorithm is O(|V|^2 + E)

* Time Comlexity of the Warshall’s algorithm is O(|V|^3)

* DFS cannot be used for finding shortest paths

* BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)

Question 5

**In the following C function, let n >= m. **

int gcd(n,m)

{

if (n%m ==0) return m;

n = n%m;

return gcd(m,n);

}

How many recursive calls are made by this function?

A : θ (n)

B : ω(n)

C : θ (loglogn)

D : θ (sqrt(n))

Answer Discuss it!

.

Correct answer is :A

Solution :

Above code is implementation of the Euclidean algorithm for finding Greatest Common Divisor (GCD).

Question 6

**What is the time complexity of the following recursive function:**

int DoSomething (int n)

{

if (n <= 2)

return 1;

else

return (DoSomething (floor(sqrt(n))) + n);

}

A : θ (n)

B : θ (n log n)

C : θ (logn)

D : θ (loglog n)

Answer Discuss it!

.

Correct answer is :D

Solution :

Recursive relation for the DoSomething() is

T(n) = T(√n) + C1 if n > 2

We have ignored the floor() part as it doesn’t matter here if it’s a floor or ceiling.

Let n = 2^m, T(n) = T(2^m)

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

From the above two, T(n) = S(m)

S(m) = S(m/2) + C1 /* This is simply binary search recursion*/

S(m) = O(logm)

= O(loglogn) /* Since n = 2^m */

Now, let us go back to the original recursive functio

Question 7

**An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?**

A : At least 2n - c comparisons, for some constant c, are needed.

B : At most 1.5n - 2 comparisons are needed

C : At least nLog2n comparisons are needed

D : None of the above

Answer Discuss it!

.

Correct answer is :B

Question 8

**Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?**

A : 0, 10, 110, 1110, 11110, 11111

B : 11, 10, 011, 010, 001, 000

C : 11, 10, 01, 001, 0001, 0000

D : 110, 100, 010, 000, 001, 111

Answer Discuss it!

.

Correct answer is :A

Solution :

We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.
The letters a, b, c, d, e, f have probabilities
1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively.
1
/
/
1/2 a(1/2)
/
/
1/4 b(1/4)
/
/
1/8 c(1/8)
/
/

Question 9

**Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of Huffman codes?**

A : 3

B : 2.1875

C : 2.25

D : 1.19375

Answer Discuss it!

.

Correct answer is :D

Solution :

We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.

The letters a, b, c, d, e, f have probabilities
1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively.
1
/
/
1/2 a(1/2)
/
/
1/4 b(1/4)
/
/
1/8 c(1/8)
/
/

Question 10

**The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is**

A : MNOPQR

B : NQMPOR

C : QMNPRO

D : QMNPOR

Answer Discuss it!

.

Correct answer is :C

Question 11

**The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity**

A : θ (n)

B : θ (m)

C : θ (m+n)

D : θ (mn)

Answer Discuss it!

.

Correct answer is :C

Solution :

Number of connected components in undirected graph can simply calculated by doing a BFS or DFS. The best possible time complexity of BFS and DFS is O(m + n).

Question 12

**Which of the following statements is true for every planar graph on n vertices?**

A : The graph is connected

B : The graph is Eulerian

C : The graph has a vertex-cover of size at most 3n/4

D : The graph has a independent set of size at least n/3

Answer Discuss it!

.

Correct answer is :C

Solution :

A planar graph is a graph which can drawn on a plan without any pair of edges crossing each other. A) FALSE: A disconnected graph can be planar as it can be drawn on a plane without crossing edges. B) FALSE: An Eulerian Graph may or may not be planar. An undirected graph is eulerian if all vertices have even degree.

Question 13

**Consider the following functions: **

f(n) = 2^{n}

g(n) = n!

h(n) = n^{logn}

Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

A : f(n) = O(g(n)); g(n) = O(h(n))

B : f(n) = Ω (g(n)); g(n) = O(h(n))

C : g(n) = O(f(n)); h(n) = O(f(n))

D : h(n) = O(f(n)); g(n) = Ω(f(n))

Answer Discuss it!

.

Correct answer is :D

Solution :

According to order of growth: h(n) < f(n) < g(n) (g(n) is asymptotically greater than f(n) and f(n) is asymptotically greater than h(n) ) We can easily see above order by taking logs of the given 3 functions

Question 14

**The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is **

A : θ (n)

B : θ (log n)

C : θ (log*n)

D : 1

Answer Discuss it!

.

Correct answer is :B

Question 15

**Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then**

A : T(n) <= 2T(n/5) + n

B : T(n) <= T(n/5) + T(4n/5) + n

C : T(n) <= 2T(4n/5) + n

D : T(n) <= 2T(n/2) + n

Answer Discuss it!

.

Correct answer is :B

Solution :

For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot. If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced.

Question 16

**The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,...,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j], 1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?**

A : X[i, j] = X[i - 1, j] V X[i, j -ai]

B : X[i, j] = X[i - 1, j] V X[i - 1, j - ai]

C : X[i, j] = X[i - 1, j] /\ X[i, j - ai]

D : X[i, j] = X[i - 1, j] /\ X[i -1, j - ai]

Answer Discuss it!

.

Correct answer is :B

Solution :

X[I, j] (2 <= i <= n and ai <= j <= W), is true if any of the following is true 1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true. 2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j.

Question 17

**Dijkstra’s single source shortest path algorithm when run from vertex a in the below graph, computes the correct shortest path distance to**

A : only vertex a

B : only vertices a, e, f, g, h

C : only vertices a, b, c, d

D : all the vertices

Answer Discuss it!

.

Correct answer is :D

Solution :

Dijkstra’s single source shortest path is not guaranteed to work for graphs with negative weight edges, but it works for the given graph.

Question 18

**We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is**

A : θ (log n)

B : θ (n)

C : θ (n logn)

D : θ (n^{2} )

Answer Discuss it!

.

Correct answer is :B

Question 19

**Let xn denote the number of binary strings of length n that contain noconsecutive 0s. Which of the following recurrences does Xn satisfy?**

A : x_{n} = 2x_{n-1}

B : x_{n}=x_{floor(n/2)} +1

C : x_{n}=x_{floor(n/2)} +n

D : x_{n}=x_{n-1}+x_{n-2}

Answer Discuss it!

.

Correct answer is :D

Question 20

**Let xn denote the number of binary strings of length n that contain noconsecutive 0s.The value of X5 is**

A : 5

B : 7

C : 8

D : 16

Answer Discuss it!

.

Correct answer is :C

Solution :

Since, X(n) = X(n - 1) + X(n - 2)

X5 = X4 + X3

X4 = X3 + X2 = 5 + 3 = 8

Therefore, X5 = 8 + 5 = 13

Question 21

**The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,...,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j],1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?**

A : X[i, j] = X[i - 1, j] V X[i, j -ai]

B : X[i, j] = X[i - 1, j] V X[i - 1, j - ai]

C : X[i, j] = X[i - 1, j] V X[i, j - ai]

D : X[i, j] = X[i - 1, j] V X[i -1, j - ai]

Answer Discuss it!

.

Correct answer is :B

Solution :

X[I, j] (2 <= i <= n and ai <= j <= W), is true if any of the following is true 1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true. 2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j.

Question 22

**The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,...,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j],1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W? Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?**

A : X[1, W]

B : X[n, 0]

C : X[n, W]

D : X[n-1, n]

Answer Discuss it!

.

Correct answer is :C

Solution :

If we get the entry X[n, W] as true then there is a subset of {a1, a2, .. an} that has sum as W.

Question 1

.

Correct answer is :D

Solution :

1 appears after 2 and 3 which is not possible in Topological Sorting.

Question 2

.

Correct answer is :A

Solution :

Worst case complexities for the above sorting algorithms are as follows:

Merge Sort - nLogn

Bubble Sort - n^2

Quick Sort - n^2

Selection Sort - n^2

Question 3

.

Correct answer is :B

Solution :

Let us put values 1, 3, 8, 10 in the hash of size 7.

Initially, hash table is empty

- - - - - - -

0 1 2 3 4 5 6

The value of function (3x + 4)mod 7 for 1 is 0, so let us put the value at 0

1 - - - - - -

0 1 2 3 4 5 6

The value of function (3x + 4)mod 7 for 3 is 6, so let us put the value at 6

1 - - - - - 3

0 1 2 3 4 5 6

The value o

Question 4

.

Correct answer is :D

Solution :

* Time Comlexity of the Dijkstra’s algorithm is O(|V|^2 + E)

* Time Comlexity of the Warshall’s algorithm is O(|V|^3)

* DFS cannot be used for finding shortest paths

* BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)

Question 5

int gcd(n,m)

{

if (n%m ==0) return m;

n = n%m;

return gcd(m,n);

}

How many recursive calls are made by this function?

.

Correct answer is :A

Solution :

Above code is implementation of the Euclidean algorithm for finding Greatest Common Divisor (GCD).

Question 6

int DoSomething (int n)

{

if (n <= 2)

return 1;

else

return (DoSomething (floor(sqrt(n))) + n);

}

.

Correct answer is :D

Solution :

Recursive relation for the DoSomething() is

T(n) = T(√n) + C1 if n > 2

We have ignored the floor() part as it doesn’t matter here if it’s a floor or ceiling.

Let n = 2^m, T(n) = T(2^m)

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

From the above two, T(n) = S(m)

S(m) = S(m/2) + C1 /* This is simply binary search recursion*/

S(m) = O(logm)

= O(loglogn) /* Since n = 2^m */

Now, let us go back to the original recursive functio

Question 7

.

Correct answer is :B

Question 8

.

Correct answer is :A

Solution :

We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.

The letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. 1 / / 1/2 a(1/2) / / 1/4 b(1/4) / / 1/8 c(1/8) / /

Question 9

.

Correct answer is :D

Solution :

We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.

The letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. 1 / / 1/2 a(1/2) / / 1/4 b(1/4) / / 1/8 c(1/8) / /

Question 10

.

Correct answer is :C

Question 11

.

Correct answer is :C

Solution :

Number of connected components in undirected graph can simply calculated by doing a BFS or DFS. The best possible time complexity of BFS and DFS is O(m + n).

Question 12

.

Correct answer is :C

Solution :

A planar graph is a graph which can drawn on a plan without any pair of edges crossing each other. A) FALSE: A disconnected graph can be planar as it can be drawn on a plane without crossing edges. B) FALSE: An Eulerian Graph may or may not be planar. An undirected graph is eulerian if all vertices have even degree.

Question 13

f(n) = 2

^{n}

g(n) = n!

h(n) = n

^{logn}

Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

.

Correct answer is :D

Solution :

According to order of growth: h(n) < f(n) < g(n) (g(n) is asymptotically greater than f(n) and f(n) is asymptotically greater than h(n) ) We can easily see above order by taking logs of the given 3 functions

Question 14

.

Correct answer is :B

Question 15

.

Correct answer is :B

Solution :

For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot. If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced.

Question 16

.

Correct answer is :B

Solution :

X[I, j] (2 <= i <= n and ai <= j <= W), is true if any of the following is true 1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true. 2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j.

Question 17

.

Correct answer is :D

Solution :

Dijkstra’s single source shortest path is not guaranteed to work for graphs with negative weight edges, but it works for the given graph.

Question 18

.

Correct answer is :B

Question 19

.

Correct answer is :D

Question 20

.

Correct answer is :C

Solution :

Since, X(n) = X(n - 1) + X(n - 2)

X5 = X4 + X3

X4 = X3 + X2 = 5 + 3 = 8

Therefore, X5 = 8 + 5 = 13

Question 21

.

Correct answer is :B

Solution :

X[I, j] (2 <= i <= n and ai <= j <= W), is true if any of the following is true 1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true. 2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j.

Question 22

.

Correct answer is :C

Solution :

If we get the entry X[n, W] as true then there is a subset of {a1, a2, .. an} that has sum as W.