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?

Tests for various other programming languages and subjects: