IT ADA

 

1.      Explain why analysis of algorithms is important? Explain: Worst Case, Best Case & Average Case Complexity.

2.      Give the properties of Heap Tree. Sort the following data with Heap Sort Method:

65, 75, 5, 55, 25, 30, 90, 45, 80.

3.      What is Divide and Conquer Technique? Give the use of it for Binary Searching Method. Also give its Time Complexity.

4.      Explain Quick Sort Method with example. Give its Time Complexity.

5.      Define Minimal Spanning Tree(MST). Explain Krushkal’s Algorithm to find MST with example.

6.      Solve the following Knapsack Problem.

W = 100

Object	1	2	3	4	5
Weight (w)	10	20	30	40	50
Value (v)	20	30	66	40	60

 7. What is an algorithm? Explain characteristics of any algorithm.

 8. Explain why analysis of algorithms is important? Arrange the following growth rate in increasing order: n³, 1, n², nlog(n), n2log(n), log(n), n^0.5

9. Explain Krushkal’s Algorithm to find Minimum Spanning Tree with example.

10. Explain Prim’s Algorithm to find Minimum Spanning Tree with example.

11. Give the properties of Heap Tree. Sort the following data with Heap Sort

Method: 20, 50, 30, 75, 90, 60, 25, 10, 40.

12.Write a program/algorithm of Quick Sort Method and analyze it.

13. Explain the use of Divide and Conquer Technique for Binary Search Method. What is the complexity of Binary Search Method?

14.  Answer the following.

(a) Solve the following 0/1 Knapsack Problem using Dynamic Programming

Method. Write the equation for solving the problem.

n = 5, W = 11

Object _ 1 2 3 4 5

Weight (w) _ 1 2 5 6 7

Value (v) _ 1 6 18 22 28

15. Explain Bubble sort algorithm. Derive the algorithmic complexity in Best case, worst case and Average case analysis.
16. Explain master theorm and solve the following recurrence equation with master method. 1. T(n)= 9T(n/3) + n 2. T(n)= 3T(n/4) + nlgn
17.  Explain Binary search algorithm with divide and conquer strategy and use the recurrence tree to show that the solution to the binary search recurrence T(n)= T(n/2) + O(1) is T(n) = O(lgn).
18. Find Minimum Spanning Tree for the given graph using Prim’s Algo. (initialization from node A)

19. Explain how to apply the divide and conquer strategy for sorting the elements using quick sort with example. Write algorithm for quick sort method.

20. Explain different asymptotic notations in brief.

21. Explain in brief characteristics of greedy algorithms

22. Design and analyze quick sort algorithm using divide and conquer technique.

23. Consider the following undirected weighted graph. Find minimum spanning tree for the same using Kruskal’s algorithm.

24. What is a fractional knapsack problem? Design and analyze greedy algorithm to solve it.

25. Write and analyze Prim’s algorithm to generate minimum spanning Tree

26. Compare Iterative and Recursive algorithm to find out Fibonacci series.

27. Explain why analysis of algorithms is important? Explain: Worst Case, Best Case & Average Case Complexity.

28. Write a program/algorithm of Selection Sort Method. What is Complexity of the method?

29.  Sort the letters of word “DESIGN” in alphabetical order using bubble sort.

30. Using greedy algorithm find an optimal schedule for following jobs with n=7

profits: (P1,P2,P3,P4,P5,P6,P7) = (3,5,18,20,6,1,38) and

deadline (d1,d2,d3,d4,d5,d6,d7) = (1,3,3,4,1,2,1)

31. Answer the following

(i) Find big theta(Ө) and big omega(Ω) notation.

(1) f(n) = 14 * 7 + 83. (2) f(n) = 83n3 + 84n

(ii) Is 2n+1 = Ο(2n) ? Explain.

32. Answer the following

(i) Prove that (n + a)b = Ө( nb) , b>0

(ii) Find big oh(Ο) notation for following:

(1)   f(n) = 6993 (2) f(n) = 6n2 + 135

33. Find the minimum and maximum element from given array using Divide & Conquer method.