12-07-2010, 03:58 PM
[FONT="]CS502-Fundamentals Of Algorithms[/FONT]
[FONT="]Fall 2010 Mid Paper 06, Dec 2010[/FONT]
[FONT="]1. [/FONT]
[FONT="]2. [/FONT][FONT="]Random access machine or RAM is a/an[/FONT]
[FONT="]3. [/FONT][FONT="]An algorithm is a (n) *********_______________[/FONT]
[FONT="]4. [/FONT][FONT="]What type of instructions Random Access Machine (RAM) can execute? Choose best answer[/FONT]
[FONT="]5. [/FONT][FONT="]What is the asymptotic growth of [/FONT][FONT="]?[/FONT]
[FONT="]6. [/FONT][FONT="]What is the asymptotic growth of [/FONT][FONT="]?[/FONT]
7. A symptotic notation is used to calculate upper bound only.
[FONT="]8. [/FONT][FONT="]If an algorithm has a complexity of 5n[/FONT][FONT="]+ log2[/FONT][FONT="]( log2[/FONT][FONT="]n[/FONT][FONT="] )+ 10[/FONT][FONT="] 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[/FONT]
[FONT="]9. [/FONT][FONT="]For the sieve technique we solve the problem[/FONT]
[FONT="]10. [/FONT][FONT="]What is the Heap – order property of max-heap?[/FONT]
[FONT="]11. [/FONT][FONT="]What is the total time to heapify?[/FONT]
[FONT="]12. [/FONT][FONT="]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[/FONT]
[FONT="]13. [/FONT][FONT="]Counting sort assumes that the numbers to be sorted are in the range 1 to k, where k is[/FONT]
[FONT="]14. [/FONT][FONT="]Counting sort algorithm sorts in[/FONT]
[FONT="]15. [/FONT][FONT="]Dynamic programming algorithms need to store the results of intermediate sub-problems.[/FONT]
[FONT="]16. [/FONT][FONT="]Matrix multiplication is An associative but not commutative operation[/FONT]
[FONT="]17. [/FONT][FONT="]We can find the product A x B of matrices A and B, only if they are compatible which means,[/FONT]
[FONT="]18. [/FONT][FONT="]Matrix – Chain – Order is __________ than the exponential time method of enumerating all possible parenthesizations and checking each one.[/FONT]
[FONT="]19. [/FONT][FONT="]Consider the following Algorithm:[/FONT]
[FONT="]Factorial (n){[/FONT]
[FONT="]if (n=1)[/FONT]
[FONT="]return 1[/FONT]
[FONT="]else[/FONT]
[FONT="]return (n * Factorial(n-1))[/FONT]
[FONT="]20. [/FONT][FONT="]The recurrence relation of Tower of Hanoi is given below [/FONT]
[FONT="]21. [/FONT][FONT="]In order to move a tower of 4 rings from one peg to another, how many ring moves are required?[/FONT]
[FONT="]22. [/FONT][FONT="]Time complexity of chain matrix multiplication is Θ (n3) and space complexity is[/FONT]
[FONT="]23. [/FONT][FONT="]How Plagiarism Detection can be done with edit distance?[/FONT]
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.
Dynamic programming design involves 4 major steps:
· 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.
[FONT="]24. [/FONT][FONT="]What is heap and what is heap order?[/FONT]
[FONT="]Solve it,[/FONT]
[FONT="][/FONT]
[FONT="]25. [/FONT][FONT="]What are Catalan numbers? Give the formula.[/FONT]
[FONT="]26. [/FONT][FONT="]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.[/FONT]
114 243 563 871 334 442 765
[FONT="]Show the result after the first pass.[/FONT]
27. [FONT="]Write down the steps of dynamic programming strategy.[/FONT]
Images are not shown here. Please download the attachment