CS502 - Mid term Dec-2009

fib (8) recrucive tree 10 marks ka question from last lecs
quick sort algorithim pesudo code 5 marks
what is geometric series 1 mark
what is selection problem 3 marks

Other Paper

Took CS502 Exam yesterday, i could remember 18 question out of 22 which are as follows:-Design and Alnalysis of Algorithms (CS502) (MID-2009-December)1. The sieve technique works in___________as follows:• Phases• Numbers• Integers• Routines2. Divide and Conquer is breaking the problem into a small number of • Pivot• Sieve• Smaller Subproblems• Selection3. What is the solution to the recurrence T(n)=T(n/2)+n,T(1)=1• O(log n)• O(n)• O(n log n)• O(2n)4. Matrix multiplication is • Neither Associative nor commutative• Associative but not commutative• Associative and commutative• Commutative but not Associative5. Due to left complete nature of binary tree, the heap can be stored in • Arrays• Structures• Link List• Stack6. What is the solution to the recurrence T(n)=T(n/2)+n T(1)=1• O(logn)• O(n)• O(n log n)• O(n2)7. What is the total time to heapify• O(log n)• O(n log n)• O(n2 logn)• O(log2n)8. What is true for Quick Sort• Stable but not inplace• Not Stable not in place• Stable and In place9. In counting sort if k is Θ (n), then counting sort is an____________time algorithm.• Θ(n)• Θ(n-k)• Θ(n+k)• Θ(n2)10. For sorting algorithms, which one is the efficient algorithm having running time.• O(n log n)• O(n2 log n)• o(n3)• Θ(n2)11. Merge sort is stable sort but not an inplace algorithm• True• False12. In the analysis of selection algorithm, we make a number of passes, in fact it could be as many as • Θ(n)• Θ(n/2)• Log n/2+n/413. Sove it q=2T(n)= 1/2 Σ (T(q-1)+T(2-q)+2)q=114. Define the notation Θ()15. How bubble sort works16. What are properties of algorithms17. What is Asymptotic notation, what are its types.18. Find maximum solution of knapsack problemCapacity of knapsack=5Items[1..4]={3,4,5,6}Weights[1..4]={2,3,4,5}