# Thread: MY CS502 Mid paper 06 DEC 2010

1. ## MY CS502 Mid paper 06 DEC 2010

CS502-Fundamentals Of Algorithms
Fall 2010 Mid Paper 06, Dec 2010

1.
2. Random access machine or RAM is a/an
3. An algorithm is a (n) *********_______________
4. What type of instructions Random Access Machine (RAM) can execute? Choose best answer
5. What is the asymptotic growth of ?
6. What is the asymptotic growth of ?
7. A symptotic notation is used to calculate upper bound only.
8. If an algorithm has a complexity of 5n+ log2( log2n )+ 10 for some model of computation (some set of assumptions) and some complexity measures (such as number of comparison operations) we could say that it has complexity
9. For the sieve technique we solve the problem
10. What is the Heap – order property of max-heap?
11. What is the total time to heapify?
12. The running time of Quick sort depends on the partitioning of the sub-arrays; if they are unbalanced, then Quick sort can run as slowly as
13. Counting sort assumes that the numbers to be sorted are in the range 1 to k, where k is
14. Counting sort algorithm sorts in
15. Dynamic programming algorithms need to store the results of intermediate sub-problems.
16. Matrix multiplication is An associative but not commutative operation
17. We can find the product A x B of matrices A and B, only if they are compatible which means,
18. Matrix – Chain – Order is __________ than the exponential time method of enumerating all possible parenthesizations and checking each one.
19. Consider the following Algorithm:
Factorial (n){
if (n=1)
return 1
else
return (n * Factorial(n-1))

20. The recurrence relation of Tower of Hanoi is given below

21. In order to move a tower of 4 rings from one peg to another, how many ring moves are required?
22. Time complexity of chain matrix multiplication is Θ (n3) and space complexity is
23. How Plagiarism Detection can be done with edit distance?
A heap is a partially sorted binary tree. Although a heap is not completely in order, it conforms to a sorting principle: every node has a value less (for the sake of simplicity, we will assume that all orderings are from least to greatest) than either of its children.
· Develop a mathematical notation that can express any solution and subsolution for the problem at hand.
· Prove that the Principle of Optimality holds.
· Develop a recurrence relation that relates a solution to its subsolutions, using the math notation of step 1. Indicate what the initial values are for that recurrenec relation, and which term signifies the final solution.
· Write an algorithm to compute the recurrence relation.
24. What is heap and what is heap order?
Solve it,

25. What are Catalan numbers? Give the formula.
26. We covered radix sort briefly in the lectures. Carry out radix sort on the following 3-digit numbers in order to sort them in ascending order.
114 243 563 871 334 442 765
Show the result after the first pass.
27. Write down the steps of dynamic programming strategy.