### SET 3

Question 1

**An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 :n - 1] is given below.**

Let L_{i} denote the length of the longest monotonically increasing sequence starting at index i in the array

Initialize L_{n-1} =1 For all i such that 0 <= i <= n-2

Finally the length of the longest monotonically increasing sequence is Max( L_{0} ,L_{1} ,...,L _{n-1}) . Which of the following statements is TRUE?

A : The algorithm uses dynamic programming paradigm

B : The algorithm has a linear complexity and uses branch and bound paradigm

C : The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm

D : The algorithm uses divide and conquer paradigm.

Answer Discuss it!

.

Correct answer is :A

Question 2

**Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4? **

f_{1}(n) = 2^{n} ; f_{2}(n) =n^{3/2}; f_{3}(n) = n log_{2}n; f_{4}(n) = n^{log n}

A : f_{3} , f_{2}, f_{4}, f_{1}

B : f_{3},f_{2},f_{1},f_{4}

C : f_{2},f_{3},f_{1},f_{4}

D : f_{2},f_{3},f_{4},f_{1}

Answer Discuss it!

.

Correct answer is :A

Question 3

**Four matrices M1, M2, M3 and M4 are dimensions p × q, q × r, r × s and s × t respectively can be multiplied in several ways with different number of total scalar multiplications. For example When multiplied as (( M1 * M2) ( M3* M4 )) the total number of scalar multiplications is pqr+rst+prt. When multiplied as (((M1 * M2 )*M3 )*M4 ) , the total number of scalar multiplications is pqr+prs+pst. If p=10, q=100, r=20, s=5 and t=80, then the minimum number of scalar multiplications needed is**

A : 24800

B : 44000

C : 19000

D : 25000

Answer Discuss it!

.

Correct answer is :C

Solution :

We can get (M1 * (M2 * M3) ) * M4) = The total number of scalar multiplication is = qrs + pqs + pst =10000 + 5000 + 4000 = 19000

Question 4

**Consider the following recursive C function that takes two arguments**

unsigned int foo ( unsigned int n, unsigned int r ) {

if (n > 0 ) return (n%r) + foo ( n / r, r )) ;

else return 0;

}

What is the return value of the function foo when it is called as foo (513, 2)?

A : 9

B : 8

C : 5

D : 2

Answer Discuss it!

.

Correct answer is :D

Question 5

**Consider the following recursive C function that takes two arguments**

unsigned int foo ( unsigned int n, unsigned int r ) {

if (n > 0 ) return (n%r) + foo ( n / r, r )) ;

else return 0;

}

What is the return value of the function foo when it is called as foo (345, 10)?

A : 345

B : 12

C : 5

D : 3

Answer Discuss it!

.

Correct answer is :B

Question 6

**An undirected graph G(V,E) contains n ( n >2 ) nodes named v1 , v2 ,....vn . Two nodes vi , vj are connected if and only if 0 < |i - j| <= 2. Each edge ( vi ,vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below. **

What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?

A : 1/12 (11n^{2}-5n)

B : n^{2} -n +1

C : 6n -11

D : 2n +1

Answer Discuss it!

.

Correct answer is :B

Question 7

**An undirected graph G(V,E) contains n ( n >2 ) nodes named v1 , v2 ,....vn . Two nodes vi , vj are connected if and only if 0 < |i - j| <= 2. Each edge ( vi ,vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below. **

The length of the path from v5 to v6 in the MST of previous question with n = 10 is

A : 11

B : 25

C : 31

D : 41

Answer Discuss it!

.

Correct answer is :C

Solution :

12 + 8 + 4 + 3 + 6 + 10 = 31

Question 8

**Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?**

A : A(n) =Ω(W(n))

B : A(n) = θ (W(n))

C : A(n) = O(W(n))

D : A(n) = o(W(n))

Answer Discuss it!

.

Correct answer is :C

Solution :

The average case time can be lesser than or even equal to the worst case. So A(n) would be upper bounded by W(n) and it will not be strict upper bound as it can even be same.

Question 9

**The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is**

A : T(n) = 2T(n - 2) + 2

B : T(n) = 2T(n - 1) + n

C : T(n) = 2T(n/2) + 1

D : T(n) = 2T(n - 1) + 1

Answer Discuss it!

.

Correct answer is :D

Solution :

Let the three pegs be A,B and C, the goal is to move n pegs from A to C using peg B The following sequence of steps are executed recursively 1.move n-1 discs from A to B. This leaves disc n alone on peg A --- T(n-1)

2.move disc n from A to C---------1

3.move n-1 discs from B to C so they sit on disc n----- T(n-1)

So, T(n) = 2T(n-1) +1

Question 10

**The worst case running time to search for an element in a balanced binary search tree with n2**^{n} elements is

A : θ (n log n)

B : θ (n 2^{n})

C : θ (n)

D : θ (log n)

Answer Discuss it!

.

Correct answer is :C

Solution :

The worst case search time in a balanced BST on ‘x’ nodes is logx. So, if x = n2^{n}, then log(n2^{n}) = logn + log(2^{n}) = logn + n = θ(n)

Question 11

**Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.**

A : SDT

B : SBDT

C : SACDT

D : SACET

Answer Discuss it!

.

Correct answer is :D

Question 12

**A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is**

A : O( n log n)

B : O( n^{2} log n)

C : O( n^{2} + log n )

D : O( n^{2} )

Answer Discuss it!

.

Correct answer is :B

Solution :

The height of the recursion tree using merge sort is logn and n^{2} comparisons are done at each level, where at most n pairs of strings are compared at each level and n comparisons are required to compare any two strings, So the worst case running time is O(n^{2} log n)

Question 13

**Let G be a weighted graph with edge weights greater than one and G’ be the graph constructed by squaring the weights of edges in G. Let T and T’ be the minimum spanning trees of G and G’ respectively, with total weights t and t’. Which of the following statements is TRUE?**

A : T’ = T with total weight t’ = t^{2}

B : T’ = T with total weight t’ < t^{2}

C : T’ ≠ T but total weight t’ = t^{2}

D : None of the above

Answer Discuss it!

.

Correct answer is :D

Solution :

Graph G is counter example for options (B) and (C) and Graph G1 is counter example for option (A)

Question 14

**What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?**

A : θ (n^{2})

B : θ (n^{2} logn)

C : θ (n^{3})

D : θ (n^{3} logn)

Answer Discuss it!

.

Correct answer is :C

Solution :

Bellman-ford time complexity: θ( |V| × |E| )

For complete graph : |E| = n(n-1)/2

|V| = n

θ (n * n(n-1)/2) = θ (n^{3})

Question 15

**A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero(the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero? **

A : This algorithm is equivalent to the first-come-first-serve algorithm

B : This algorithm is equivalent to the Round Robin algorithm

C : This algorithm is equivalent to the shortest-job-first algorithm

D : This algorithm is equivalent to the shortest-remaining-time-first algorithm

Answer Discuss it!

.

Correct answer is :B

Solution :

The given scheduling definition takes two parameters, one is dynamically assigned process priority and the other is ‘T’ time unit to re-evaluate the process priorities.

This dynamically assigned priority will be deciding processes order in ready queue of round robin algorithm whose time quantum is same as ‘T’ time units. As all the processes are arriving at the same time, they will be given same priority but soon after first ‘T’ time burst remaining processes will get higher priorities

Question 16

**Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?**

A : O(log n)

B : O(n)

C : O(n log n)

D : O(n^{2})

Answer Discuss it!

.

Correct answer is :B

Solution :

The maximum number of swaps that takes place in selection sort on n numbers is n

Question 17

**Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter **

MultiDequeue (Q) {

m =k

while (Q is not empty) and (m >0) {

Dequeue (Q)

m = m - 1

}

}

What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue?

A : θ (n)

B : θ (n+k)

C : θ (nk)

D : θ (n^{2})

Answer Discuss it!

.

Correct answer is :A

Solution :

Initially the queue is empty and we have to perform n operations.

i) One option is to perform all Enqueue operations i.e. n Enqueue operations. Complexity will be θ(n)

or

ii) We can perform a mix of Enqueue and Dequeue operations. It can be Enqueue for first n/2 times and then Dequeue for next n/2

Question 18

**The number of elements that can be sorted in θ(logn) time using heap sort is**

A : θ (1)

B : θ (√log n)

C : θ (log n/ log logn)

D : θ (log n)

Answer Discuss it!

.

Correct answer is :A

Solution :

After constructing a max-heap in the heap sort , the time to extract maximum element and then heapifying the heap takes θ(log n) time by which we could say that θ(log n) time is required to correctly place an element in sorted array. If θ(logn) time is taken to sort using heap sort, then number of elements that can be sorted is constant which is θ(1)

Question 1

Let L

_{i}denote the length of the longest monotonically increasing sequence starting at index i in the array

Initialize L

_{n-1}=1 For all i such that 0 <= i <= n-2

Finally the length of the longest monotonically increasing sequence is Max( L

_{0},L

_{1},...,L

_{n-1}) . Which of the following statements is TRUE?

.

Correct answer is :A

Question 2

f

_{1}(n) = 2

^{n}; f

_{2}(n) =n

^{3/2}; f

_{3}(n) = n log

_{2}n; f

_{4}(n) = n

^{log n}

.

Correct answer is :A

Question 3

.

Correct answer is :C

Solution :

We can get (M1 * (M2 * M3) ) * M4) = The total number of scalar multiplication is = qrs + pqs + pst =10000 + 5000 + 4000 = 19000

Question 4

unsigned int foo ( unsigned int n, unsigned int r ) {

if (n > 0 ) return (n%r) + foo ( n / r, r )) ;

else return 0;

}

What is the return value of the function foo when it is called as foo (513, 2)?

.

Correct answer is :D

Question 5

unsigned int foo ( unsigned int n, unsigned int r ) {

if (n > 0 ) return (n%r) + foo ( n / r, r )) ;

else return 0;

}

What is the return value of the function foo when it is called as foo (345, 10)?

.

Correct answer is :B

Question 6

What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?

.

Correct answer is :B

Question 7

The length of the path from v5 to v6 in the MST of previous question with n = 10 is

.

Correct answer is :C

Solution :

12 + 8 + 4 + 3 + 6 + 10 = 31

Question 8

.

Correct answer is :C

Solution :

The average case time can be lesser than or even equal to the worst case. So A(n) would be upper bounded by W(n) and it will not be strict upper bound as it can even be same.

Question 9

.

Correct answer is :D

Solution :

Let the three pegs be A,B and C, the goal is to move n pegs from A to C using peg B The following sequence of steps are executed recursively 1.move n-1 discs from A to B. This leaves disc n alone on peg A --- T(n-1)

2.move disc n from A to C---------1

3.move n-1 discs from B to C so they sit on disc n----- T(n-1)

So, T(n) = 2T(n-1) +1

Question 10

^{n}elements is

.

Correct answer is :C

Solution :

The worst case search time in a balanced BST on ‘x’ nodes is logx. So, if x = n2

^{n}, then log(n2

^{n}) = logn + log(2

^{n}) = logn + n = θ(n)

Question 11

.

Correct answer is :D

Question 12

.

Correct answer is :B

Solution :

The height of the recursion tree using merge sort is logn and n

^{2}comparisons are done at each level, where at most n pairs of strings are compared at each level and n comparisons are required to compare any two strings, So the worst case running time is O(n

^{2}log n)

Question 13

.

Correct answer is :D

Solution :

Graph G is counter example for options (B) and (C) and Graph G1 is counter example for option (A)

Question 14

.

Correct answer is :C

Solution :

Bellman-ford time complexity: θ( |V| × |E| )

For complete graph : |E| = n(n-1)/2

|V| = n

θ (n * n(n-1)/2) = θ (n

^{3})

Question 15

.

Correct answer is :B

Solution :

The given scheduling definition takes two parameters, one is dynamically assigned process priority and the other is ‘T’ time unit to re-evaluate the process priorities.

This dynamically assigned priority will be deciding processes order in ready queue of round robin algorithm whose time quantum is same as ‘T’ time units. As all the processes are arriving at the same time, they will be given same priority but soon after first ‘T’ time burst remaining processes will get higher priorities

Question 16

.

Correct answer is :B

Solution :

The maximum number of swaps that takes place in selection sort on n numbers is n

Question 17

MultiDequeue (Q) {

m =k

while (Q is not empty) and (m >0) {

Dequeue (Q)

m = m - 1

}

}

What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue?

.

Correct answer is :A

Solution :

Initially the queue is empty and we have to perform n operations.

i) One option is to perform all Enqueue operations i.e. n Enqueue operations. Complexity will be θ(n)

or

ii) We can perform a mix of Enqueue and Dequeue operations. It can be Enqueue for first n/2 times and then Dequeue for next n/2

Question 18

.

Correct answer is :A

Solution :

After constructing a max-heap in the heap sort , the time to extract maximum element and then heapifying the heap takes θ(log n) time by which we could say that θ(log n) time is required to correctly place an element in sorted array. If θ(logn) time is taken to sort using heap sort, then number of elements that can be sorted is constant which is θ(1)