MODEL PAPER DESIGN AND ANALYSIS OF ALGORITHMS

contributed by AUTHOR: Prof Gajendra Sharma

(This model paper has been designed for practice purpose only and author and publisher have no legal obligations if the same questions appears in the university exam. )

(BTECH / MCA )
Note : Few questions are extra which is not the part of BTECH Syllabus,



Q1. Discuss the Analysis of Selection Sort Algorithm?
Q2. Execute the Merge Sort/ Quicksort on given data(data as provided)?
Q3. Give the Counting Sort Algorithm?
Q4.Show that n/k sublists , each of length k can be sorted by insertion sort in Ө(nk) worst case time?
Q5. Prove the following
(i) log(n!) = Ө(nlogn)
(ii) (n+a) pow(b) = Ө( n pow(b) )
Q6. Find each asymptotic of the following
(i) f(n) = n pow(10) ; g(n) = 2 pow( n/2)
(ii) f(n) = n pow(3/2) ; g(n) = n log(pow(2)) (n)
(iii) f(n) = log (n pow(3)) ; g(n) = log(n)
(iv) f(n) = log( 3pow( n)) ; g(n) = (log 2pow(n))
Q7. Prove using the asymptotic definition of theta notation
F(N) + G(N) = MAX( Ө (F(N), G(N))
Q8. Insert the following keys into an initially empty AVL Tree
30, 40, 24, 11, 13, 10, 58, 26, 48
Q9. Solve the Following Recurrence
(i) T(n) = T(n-1) + n 4
(ii) T( n) = T(n/2) + T (n/3 ) + n
(iii) T (n) = 3T ( n 1 / 3) + log 3 n
(iv) T ( n) = T (an) + T ((1-a)n) + n




Q10. Write HEAP-DELETE(A, i) which deletes the item in in node i from heap A..

Q11. Prove that the heap can be constructed in Ό(n) time.

Q12. Rank the following in the order of growth :-
(3/2)pow(n) , (2/3)pow(n), 2pow(2pow(n)) , e pow(n) , 2n!
Q13. Prove that any decision tree that sorts n elements has height Ω( nlogn)

Q14. Show that there are floor(3n/) – 2 comparisons are necessary for finding maximum and minimum of n numbers simultaneously.

Q15.Problems on INORDER, PREORDER, POSTORDER Traversal.

Q16. Construct a Binary Tree from the following
INORDER : E A C K F H D B G
PREORDER : F A E K C D H G B
Q16. Write an algorithm for QUEUE using two STACKS.
Q17. In a 2-Tree if n(E) is number of external nodes and n(I) is the number of internal nodes then prove that n(E) = n(I) + 1, if E and I are external and internal path lengths and n is the number of internal nodes.

Q18 Prove that height of binary tree is logn.

Q19. Define RB-Tree and Give the algorithm for RB-TREE-INSERT

Q20. Give RB-TREE-COLR-FIX-UP ALGO

Q21. How do we AUGMENT the Data Structure , explain and give appropriate algorithms to prove it.

Q22. What do you mean by Dynamic Programming , explain with example.

Q23. Give the LCS Algorithm using Dynamic Programming.

Q24. Solve the following using TSP using the branch and bound Technique.

Q25. Give the GRAPH COLORING Algorithm.

Q26. Give the BFS/DFS Algorithm ?


Q27. Find the optimal solution to the knapsack instance and also give the greedy-knapsack algorithm
(P1,P2,P3,P4,P5,P6,P7)=(10,5,15,7,6,18,3), (W1,W2,W3,W4,W5,W6,W7)= (2,3,5,7,1,4,1)

Q28. what do you mean by amortized cost , give the MULTIPOP Algoithm.

Q29. Show the result of inserting the following keys into an empty B-Tree
F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E, G, I of order 5.

Q30. Define Binomial Heap and Give algorithm for BINOMIAL-HEAP-UNION?

Q31. Give the FIBONACCI-HEAP-DELETE Algorithm?

Q32. Define the following:-
Strongly Connected Graph, Articulation Points, Bridges

Q33. Give an efficient Algorithm to prove that the graph is Bipartite?

Q34. Give the Correctness of PRIM’s and KRUSKAL Algorithm

Q34. How Will you detect a CYCLE in the given graph , Give the Algorithm for it?

Q34. Give the NQUEENS Algorithm ?

Q35. Solve the given graph for finding MST and give its Algorithm?

Q36. Give the Belman Ford Algorithm ?

Q37. Modify the Floyd-Warshal Algorithm for detecting Cycle in the graph?

Q38. Solve the given graph for finding the Maximum Flow?

Q39. What is Bitonic Sorting Network, explain.

Q40. Explain Chinese Remainder Theorem

Q41. Give the Strassen’s Matrix Multiplication Algorithm ?

Q42. Define NP, NP-Complete and NP-Hard problem

Q43. Give the Subset Sum Algorithm.


Q44. What is Clique , prove that it NP Problem

Q45. Find the prefix of the following and give COMPUTE-PREFIX Algorithm
“ababababca”
Q46. What is Convex Hul Give the Graham Scan’s Algorithm?

Q47. Give the RSA Cryptography Algorithm?

Q48. Give the Euclid Algorithm?

Q49. Give the FFT Algorithm?

Q50. Draw 11- item hash table resulting from hashing the keys 12, 4, 13, 88, 23, 94, 11, 39, 20, 16 and 5 using the hash function h(i) = (2i + 5) mod 11.

Q51. Define €-Approximation and Absolute Approximation?

Q52. Prove that in a k – ordered Binomial Tree there are at most k C I nodes at level I , where C represents Binomial.