Dark Mode On/Off

# GATE 2020 - Algorithms Beginner Test

This Test will cover complete Algorithms topic with very important questions, starting off from basics to advanced level.
Q. Which Decision Procedure has atleast doubly-exponential time complexity?
 A. Linear programming B. Travelling salesman problem C. Presburger arithmetic D. Hamiltonian circuit problem
Q. The running time T(n), where 'n' is the input size of a recursive algorithm is given.
``````T(n) = c+T(n-1), if n>1
= d, if n<=1
The order of the algorithm is : ``````
 A. n * n B. n C. n * n * n D. n ^ n
Q. `f(n)` is of the order of `g(n)` if there exist positive integers "a" and "b" such that?
 A. f(n) <= a*g(n) for all n>=b B. f(n) <= a*g(n) for all n<=b C. g(n) <= a*f(n) for all n>=b D. None of these
Q. The complexity of comparison based sorting algorithms is __________ ?
 A. Theta(n log(n)) B. Theta(n) C. Theta(2n) D. Theta(nAn)

Q. The recurrence relation that arises in relation with the complexity of binary search is?
 A. T(n) = T(n/2)+K B. T(n) = 2T(n/2)+K C. T(n) = T(n/2)+log n D. T(n) = T(n/2)+n
Q. When `s` be a sorted array of `n` integers, and `t(n)` denote the time taken for the most efficient algorithm to determine if there are two elements with sum less than 1000 in `s`, then which of the following statements is true?
 A. t(n) is O(1) B. n <= t(n) <= n log(n) C. n log(n) <= t(n) < (n/2) D. t(n) = (n/2)
Q. Let `f,g,h,k: N->N`, If f=O(h) and g=O(k), then?
 A. f+g = O(h+k) B. fg = O(hk) C. Both (a) and (b) D. None of these
Q. For any total computable function `f:N->N`, there is a step-counting function `g` so that for every `n` __________ ?
 A. g(n) < f(n) B. g(n) > f(n) C. g(n) = f(n) D. None of these
Q. The running time of an algorithm is given by `T(n) = T(n-1)+T(n-2)-T(n-3)`, if `n > 3n`, otherwise. The order is __________ ?
 A. n B. log n C. n ^ n D. n ^ 2

Q. What should be the relation between T(1), T(2) and T(3), so that the above question gives an algorithm ?
 A. T(1) = T(2) = T(3) B. T(1) + T(3) = 2T(2) C. T(1)-T(3) = T(2) D. T(1)+T(2) = T(3)
Q. The concept of order(Big O) is important because?
 A. It can be used to decide the best algorithm that solves a given problem. B. It determines the maximum size of a problem that can be solved in a given amount of time. C. It is the lower bound of the growth rate of algorithm. D. Both (a) and (b)
Q. The algorithm design technique used in the Quick Sort algorithm is?
 A. Dynamic programming B. Backtracking C. Divide and conquer D. Greedy method
Q. A hash table can store a maximum of 10 records. Currently there are records in locations 1,3,4,7,8,9,10. The probability of a new record going into location 2, with a hash function resolving collisions by linear probing is __________ ?
 A. 0.6 B. 0.1 C. 0.2 D. 0.5
Q. Consider a hashing function that resolves collision by Quadratic Probing. Assume the address space is indexed from 1 to 8. If a collision occurs at position 4, then the location which will never be probed is?
 A. 4 B. 5 C. 8 D. 2
Q. A hash table has space for 100 records. Then the probability of collision before the table is 10% full, is?
 A. 0.45 B. 0.5 C. 0.3 D. 0.34(approximately)