1. Asymptotic growth rate of the function is taken over_________ case running time.

2. If there are Θ (n2) entries in edit distance matrix then the total running time is

3. What type of instructions Random Access Machine (RAM) can execute? Choose best answer

4. In RAM model instructions are executed

5. F (n) and g (n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.

6. In simple brute-force algorithm, we give no thought to efficiency

7. Consider the following code:
For(j=1; j<n;j++)
For(k=1; k<15;k++)
For(l=5; l<n; l++)
{
Do_something_constant();
}
What is the order of execution for this code.

8. In 2d-space a point is said to be ________if it is not dominated by any other point in that space.

9. Consider the following Algorithm: Factorial (n){ if (n=1) return 1 else
return (n * Factorial(n-1)) }
Recurrence for the following algorithm is:

10. When we call heapify then at each level the comparison performed takes time

11. Is it possible to sort without making comparisons?

12. In addition to passing in the array itself to Merge Sort algorithm, we will pass in _________other arguments which are indices.

13. The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Here Upper Bound means the function f(n) grows asymptotically ____________ faster than n log n.

14. Brute-force algorithm uses no intelligence in pruning out decisions.

15. In analysis of f (n) =n (n/5) +n-10 log n, f (n) is asymptotically equivalent to ________.

16. Counting sort the numbers to be sorted are in the range 1 to k where k is small.

17. What type of instructions Random Access Machine (RAM) can execute?

18. If we associate (x, y) integers pair to cars where x is the speed of the car and y is the negation of the price. High y value for a car means a ________ car.

19. Due to left complete nature of binary tree, the heap can be stored in

20. The Knapsack problem belongs to the domain of _______________ problems.

21. 8n2 + 2n - 3 will eventually exceed c2*(n) no matter how large we make c2.

22. What is the total time to heapify?

23. Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________

24. Algorithm is concerned with.......issues.

25. Mergesort is a stable algorithm but not an in-place algorithm

26. ______________ graphical representation of algorithm.

27. Due to left-complete nature of binary tree, heaps can be stored in

28. For small values of n, any algorithm is fast enough. Running time does become an issue when n gets large.

29. In selection algorithm, because we eliminate a constant fraction of the array with each phase, we get the

30. We cannot make any significant improvement in the running time which is better than that of brute-force algorithm.