Previous Year questions unit wise

Unit 1

1. Rank the following by growth rate

N, 2lg √n, log n, log(log n), log 2 n, (log n)log n, 4, (3/2)n, n!
2. What do you mean by stability of sorting algorithms.
3. Use recursion tree to give an asymptotically tight solution to the recurrence
T(n)=T(an)+T(1-a)n)+cn, where a is a constant in the range 0<a<1 and c>0 is also constant.
4. What is recurrence relation? How is a recurrence solved using master’s theorem?
5. What is asymptotic notation? Explain Omega (Ω) notation?
6. Solve the recurrence T (n) = 4T(n/2) + n2
7. Explain how algorithms performance is analyzed?
8. Explain searching technique using divide and conquer approach.
9. Write an algorithm for counting sort? Illustrate the operation of counting sort on the following
array: A={4, 0, 2, 0, 1, 3, 5, 4, 1, 3, 2, 3}
10. Solve the following recurrence relation:
T (n) = T (n-1) + n4
T (n) = T (n/4) + T (n/2) + n2
11. Write an algorithm for insertion sort. Find the time complexity of Insertion sort in all cases.
12.

13. How analyze the performance of an algorithm in different cases?

14. Derive the time complexity of Merge sort
15.

16. What is the advantage of binary search over linear search? Also state the limitations of binary
search.
17. Define feasible and optimal solution
18. What do you mean by polynomial time reduction
19.

20. Among merge sort, insertion sort and quick sort which of the following sorting is the best in
worst case. Apply the best one among these sorting algorithms to sort the following – E, X, A, M, P,
L, E in alphabetic order.
21.

22. Solve the recurrence

a. T (n) =3T (n/4) + cn2 using recursion tree method.
b. T (n) = n + 2T (n/2) using Iteration method. (Given T(1)=1)
23. Write Merge sort algorithm and sort the following sequence {23, 11, 5, 15, 68, 31, 4, 17}
using merge sort.
24. What do you understand by stable and unstable sorting? Sort the following sequence
{25, 57, 48, 36, 12, 91, 86, 32} using heap sort.
25. What is recurrence relation? How is a recurrence solved using master’s theorem?
26. What is asymptotic notation? Explain Omega (Ω) notation?
27.

28. How the following array A elements is sorted using heap sort A={23, 9, 18, 45,5,9,1, 17, 6}
29. Difference between Complete Binary Tree and Binary Tree?
30. Solve the following recurrence using Master method:
a. T (n) = 4T (n/3) + n2
31. Name the sorting algorithm that is most practically used and also write its Time Complexity.
32. Find the time complexity of the recurrence relation
a. T(n)= n +T(n/10)+T(7n/5)
33. Compare Time Complexity with Space Complexity.
34. What are the characteristics of the algorithm?
35. Solve the following By Recursion Tree Method
T(n)=n+T(n/5)+T(4n/5)
36. The recurrence T (n) =7T (n/2) +n 2 describe the running time of an algorithm A.
A competing algorithm A has a running time of T’ (n) =aT’ (n/4) +n 2 .What is the largest
integer value for a A’ is asymptotically faster than A?
 Unit 2
1. Prove that if n>=1, then for any n-key B Tree of height h and minimum degree t>=2,
h<= log t ((n+1)/2)
2. Write down the properties of binomial tree.
3. Insert the following information F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E,G,I into
an empty B-tree with degree t=3.
4. Show the results of inserting the keys F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y,
D, Z, E in order into an empty B-tree. Use t=3, where t is the minimum degree of B- tree.
5. Write an algorithm for insertion of key in the Red-Black Tree. Discuss the various cases
for insertion of key in red-black tree for given sequence of key in an empty red-black tree-
5, 16, 22, 25, 2, 10, 18, 30, 50, 12, 1.
6. Explain Skip list in brief.
7. Explain and write an algorithm for union of two binomial heaps and also write its time
complexity?
8. Insert the following element in an initially empty RB- Tree.
12,9,81,76,23,65,88,76,32,54. Now Delete 23 and 81.
9. Use the minimum degree t as ‘3’, insert following sequence of integers 10, 25, 20, 35, 30, 55,
40, 45, 50, 55, 60, 75, 70, 65, 80, 85 and 90 in an initially empty B tree. Give the number of
nodes splitting operations that takes place.
10. Explain the algorithm to delete a given element in a binomial heap. Give an example for the
same.
11. Explain left rotation in RB tree.
12. Write down the properties of Fibonacci Heap.
13. What is Binomial Heap? Write down the algorithm for Decrease key operation in Binomial
Heap also write its time complexity.
14. Discuss the various cases for insertion of key in red-black tree for given sequence of key in
an empty red-black tree- {15, 13, 12, 16, 19, 23, 5, 8}.
15. What is skip list? Explain the Search operation in Skip list with suitable example.
16. Insert the following in 2-3-4 B Tree 40,35,22, 90,12, 45,58, 78,67, 60 and then delete 35 and
22.
17. Explain the different conditions of getting union of existing binomial heaps. Also write the
algorithm for union of 2 binomial heaps. What is its complexity.
18. Insert the elements in the empty red black tree. 8, 20, 11, 14, 9, 4, 12 and delete 12, 4, 9,14
respectively.
19. What is Red-Black tree? Write an algorithm to insert a node in an empty red-black tree.
Explain with suitable example.
20. Explain HEAP-SORT on the array. Illustrate the operation of HEAP-SORT on the array A=
{6, 14, 3, 25, 2, 10, 20, 7, 6}
21. Explain properties of Binomial Heap. Write an algorithm to perform uniting two
Binomial Heaps. And also to find Minimum Key.
 Unit 3
1. Discuss greedy approach to an activity selection problem of scheduling several competing
activities. Solve following activity selection problem S = {A1, A2, A3, A4, A5, A6, A7, A8,
A9, A10} Si = {1, 2, 3, 4, 7, 8, 9, 9, 11, 12} Fi = {3, 5, 4, 7, 10, 9, 11, 13, 12, 14}
2. Define minimum spanning tree (MST). Write Prim’s algorithm to generate a MST for any
given weighted graph. Generate MST for the following graph using Prim’s algorithm.

3. Explain Dijkstra’s algorithm to solve single source shortest path problem with suitable
example.
4. What is travelling salesman problem (TSP)? Find the solution of following TSP using
dynamic programming.
5. 6. 7. 8.
0 1 1 6

9. 10. 11. 12.

2 0 7 3
13. 14. 15. 16.
9 6 0 1

17. 18. 19. 20.

1 4 8 0

1. What are greedy algorithms? Explain their characteristics.

2. Define spanning tree? Write Kruskal’s algorithm for finding minimum cost spanning tree.
Describe how Kruskal’s algorithm is different from Prim’s algorithm for finding minimum
spanning tree.
3. Compare the various programming paradigms such as divide and conquer, dynamic
programming and greedy approach.
4. What do you mean by convex hull? Describe an algorithm that solves the convex hull
problem. Find the time complexity of the algorithm.

5. Explain Greedy programming in brief.

6. What do you mean by convex hull?
7. Write and explain the Kruskal algorithm to find the Minimum Spanning Tree of a graph with
suitable example.

8. What is Knapsack problem? Solve Fractional knapsack problem using greedy programming
 for the following four items with their weights w = {3, 5, 9, 5} and values P = {45, 30, 45,
10} with knapsack capacity is 16.
9. Write down the Bellman Ford algorithm to solve the single source shortest path problem also
write its time complexity.

10. Prove that if the weights on the edges of the connected undirected graph are distinct then
there is a unique Minimum spanning tree. Give an example in this regard. Also discuss
Prim’s minimum spanning tree in detail.
11.

12. Difference between Greedy Technique and Dynamic programming.

13. Explain Single source shortest path.
14. What is Minimum Cost Spanning Tree? Explain Kruskal’s Algorithm and Find MST of the
Graph. Also write its Time-Complexity

15. Explain Convex –Hull problem.

16. Find the shortest path in the below graph from the source vertex 1 to all other vertices by
using Dijkstra’s algorithm.

17. Given the six items in the table below and a Knapsack with Weight 100, what is the solution
to the Knapsack problem in all concepts. I.e. explain greedy all approaches and find the
 optimal solution

Unit 4
1. Define principle of optimality. When and how dynamic programming is applicable.
2. Explain application of graph coloring
a. Define Graph Coloring.
3. Compare the adjacency matrix and linked adjacency lists representation of a graph with
suitable example. Differentiate between Backtracking and Branch and Bound Techniques.
4. What is sum of subset problem? Draw a state space tree for Sum of subset problem
using backtracking? Let n=6, m=30 and w [1:6] = {5, 10, 12, 13, 15, 18}
5. Differentiate Backtracking algorithm with branch and bound algorithm.
6. Discuss n queen’s problem. Solve 4 queen’s problem using backtracking method?
7. What is dynamic programming? How is this approach different from recursion? Explain with
example.
8. Solve the following 0/1 knap sack problem using dynamic programming p=[11,21,31,33]
w=[2,11, 22, 15] c=40 and n=4.
9. Define Floyd’s algorithm for all pair shortest path and apply the same on the following graph

10. Write down the Floyd Warshal algorithm.

11. Explain Branch and Bound method in brief
12. What is N queens problem? Draw a state space tree for 4 queens problem using backtracking.
13. What is travelling salesman problem (TSP)? Find the solution of following TSP using Branch
& Bound method
14. 15. 16. 17. 18.
0 2 3 1 1

19. 20. 21. 22. 23.

1 0 1 4 2

24. 25. 26. 27. 28.

3 5 0 2 4
29. 30. 31. 32. 33.
1 6 1 0 3

34. 35. 36. 37. 38.

1 4 7 1 0
 14 Explain the method of finding Hamiltonian cycles in a graph using backtracking
method with suitable example.
11 Solve the following sum of subset problem using backtracking where n=4, m=18
w[4]={5,10,8, 13}

12 Give Floyd Warshall algorithm to find the shortest path for all pairs of vertices in a graph.
Give the complexity of the algorithm. Explain with example.

13 What is backtracking? Discuss sum of subset problem with the help of an example.
14 Write down an algorithm to compute Longest Common Subsequence (LCS) of two given
strings and analyze its time complexity.

Unit 5
1) What are approximation algorithm? What is meant by P (n) approximation algorithms?
2) Explain Fast Fourier Transform in brief.
3) Explain Fast Fourier Transform in brief.
4) Write an algorithm for naive string matcher?
5) Define BNP, NP hard and NP Complete problems. Prove that Travelling salesman problem is
NP Complete
6) Write KMP algorithm for string matching? Perform the KMP algorithm to search the
occurrences of the pattern abaab in the text string abbabaabaabab.
7) Write short notes on following:
(i.) Randomized algorithm. (ii.) NP- complete and NP hard.
8) What is approximation algorithm? Explain set cover problem using approximation algorithm.
9) Explain the applications of FFT
10) Define NP hard and NP complete problems. What are the steps involved in proving a problem
NP Complete? Specify the problems already proved to be NP-complete.
11) Describe in detail KMP string matching algorithm. Compute the prefix function ∏ for the
pattern ‘ababbabbabbababbabb’ when the alphabet is ∑ = {a,b}
12) What is meant by P(n) approximation algorithms. Discuss approximation algorithm for
Travelling salesman problem.
14 Explain Randomized algorithm in brief.
13) Explain NP-complete and NP-Hard.
14) Write Rabin Karp string matching algorithm. Working modulo q=11, how many spurious
hits does the Rabin karp matcher in the text T= 3141592653589793, when looking for the pattern
P=26.
15) Write and explain the algorithm to solve vertex cover problem using
approximation algorithm.
16) Explain and Write the Knuth-Morris-Pratt algorithm for pattern matching also
write its time complexity.
17) Discuss the problem classes P, NP and NP –complete .with class relationship.
18) Compute the prefix function π for the pattern P= a b a c a b using KNUTH-
MORRIS –PRATT Algorithm. Also explain Naïve String Matching algorithm.
19) Explain Approximation and Randomized algorithms.