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?
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 :
Q. f(n) is of the order of g(n) if there exist positive integers "a" and "b" such that?
Q. The complexity of comparison based sorting algorithms is __________ ?
Q. The recurrence relation that arises in relation with the complexity of binary search is?
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?
Q. Let f,g,h,k: N->N, If f=O(h) and g=O(k), then?
Q. For any total computable function f:N->N, there is a step-counting function g so that for every n __________ ?
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 __________ ?
Q. What should be the relation between T(1), T(2) and T(3), so that the above question gives an algorithm ?
Q. The concept of order(Big O) is important because?
Q. The algorithm design technique used in the Quick Sort algorithm is?
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 __________ ?
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?
Q. A hash table has space for 100 records. Then the probability of collision before the table is 10% full, is?
