CS502 Fundamentals of Algorithm Midterm Paper 14 December 2012

CS502 Fundamentals of Algorithm Midterm Paper 14 December 2012
 Total Questions = 26
Total MCQ = 20 (Each of 1 Marks)
Total Short Questions = 2 (Each of 2 Marks)
Total Short Questions = 2 (Each of 3 Marks)
Total Long Questions = 2 (Each of 5 Marks)

1.An array having n elements,what is the probability of selection 1/n element as a pivot element(2 marks)
2- draw chain matrix multiplication table for initialization state(2 marks)
3- when quick sort don’t uses divide n conquer explicitly n the main procedure used in Q.S(3 marks)
4- how to calculate optimum solution for 0/1 knapsack problem(3 marks)
5-fabinocci sequnce ka question tha.n i was asked to make a recursive tree for fib(8)(5 marks)
6-an array of A1,A2,A3….An number was given.i don’t remember the statement but according to that scenario it was a stable sorting algorithm havin O(n log n) algorithm.i was asked to solve that array problem.which sortin algorithm best suits???(5 marks)

Another Paper:

What are the two steps generally involved while developing dynamic programming algorithm. (2)

How we build heap? (2)
What are the applications of edit distance technique? Name any three (3)
Solve: T(n) = (T(q − 1) + T(2 − q) + 2) (3)
What is the worst case running time for the bucket sort? What simple change is required in the algorithm to preserve its linear expected running time and makes it worst case time Θ(n log n) (5)
Given an unordered list of n x0, x1, x2, …, xn and elements is common, if there are atleast n/5 copies of it.We want to identify all the common numbers in our list. Give O(n log n) to solve the problem.