Design & Analysis of Algorithm

GATE - MCQs Part 4

PREV
NEXT
Menu

Q1- Which of the following is true

  1. An algorithm is a step-by-step process to solve a problem
  2. An algorithm is a step-by-step process for solving a problem that can be implemented in any language.
  3. To a given problem, there may be more than one algorithm used.

(a) 2 and 3

(b) 1 and 3

(c) only 3

(d) only 1

(b)

Q2- In tower of Hanoi problem, with 5 disks, how many numbers of moves are required to sort all the disks?

(a) 15

(b) 31

(c) 41

(d) 26

(b)

Tower of Hanoi problem recurrence equation

T(n) = 2T(n − 1) + 1

T(5) = 2T(4) + 1

T(4) = 2T(3) + 1

T(3) = 2T(2) + 1

T(2) = 2T(1) + 1

T(1) = 1

T(2) = 3

T(3) = 7

T(4) = 15

T(5) = 31

Q3- Two alternative packages A and B are available for processing a database having 10k records. Package A requires 0.0001n2 time units and package B requires 10n*log10(n) time units to process n records. What is the smallest value of k for which package B will be preferred over A?

(A) 12
(B) 10
(C) 6
(D) 5

(c)

Package A

Time requires = 0.0001*n2

Package B

Time requires = 10n*log10(n)

Form an equation,

=> 0.0001*n2 = 10n*log10(n)

=> n/104 = 10*log10(n)

=> n/105 = log10(n)

Substitute n = 10k

=> 10k-5 = log10(10k)

=> 10k-5 = k

If k = 5,

=> 105-5 < 5

=> 1 < 5 means package B has more time to process than package A.

If k = 6,

=> 106-5 > 6

=> 10 > 6 means package B has less time to process than package A.

Q4- Which of the following is true

  1. 25n = Big-Oh(n2)
  2. 50n2 = Big-Omega(n2)
  3. 50n3 ≠ small-oh(n3)
  4. 25n2 = Big-Oh(n2)

(a) 1, 3

(b) 1, 2, 4

(c) 1, 3, 4

(d) All are correct

(d)

Q5- Which of the following is true

  1. (½)n2 = small-omega(n)
  2. (½)n = Big-Omega(n)

(a) 1 is correct

(b) 2 is correct

(c) Both are correct

(d) None is correct

 

(c)

PREV
NEXT