MODULE 1I

1. Discuss how quick sort works to sort an array. Trace quick sort algorithm for the following
data set 65, 70, 75, 80, 85, 60, 55, 50, 45. Also derive the worst case time complexity, best
case time complexity of quick sort.
2. Write the recursive algorithm for merge sort. Analyze its time complexity.
3. Consider the following set of 14 elements in an array list -15, -6, 0, 7, 9, 23, 54, 82, 101,
112, 125, 131, 142, 151 when binary search is applied on these elements, find the elements
which required maximum number of comparisons. Also determine average number of key
comparisons for successful search and unsuccessful search.
4. Consider the number given below. Show how partitioning algorithm of quick sort will
place 106 in its correct position. Show all the steps clearly
106 117 128 134 141 91 84 63 42
5. What is Divide and Conquer method? Show that the worst case efficiency of binary search
algorithm is O(log n)
6. Explain with suitable example a sorting algorithm that uses divide and conquer technique
which divides the problem size by considering position. Give the corresponding algorithms
and analyze for time complexity.
7. Explain the advantages and disadvantages of Divide and Conquer design technique.
8. What is a stable sorting algorithm. Explain with an example
9. Is quicksort a stable sorting algorithm. Explain.
10. What is an in-place sorting algorithm? Explain with an example.
11. Write and explain the Control Abstraction for Divide and Conquer.
12. Differentiate Quicksort and Mergesort.
13. Explain the Master Theorem for Analyzing divide and conquer recurrences.Give suitable
examples.
14. Solve the following recurrences using Master Theorem.
a. T(n)=2T(n/2)+n3
b. T(n)=3T(n/2)+n2
15. List down the steps in problem solving using Divide and Conquer
16. Explain Merge sort algorithm with an example
17. Write the algorithm for Quicksort. Trace Quicksort algorithm for the following data set
615, 720, 175, 890, 085, 610, 55, 50, 45. Show the steps in the first partition.
18. Explain Divide and Conquer technique with an example
19. Write a sorting algorithm that uses Divide and Conquer technique which divides the
problem size by considering position. Trace the same algorithm for the following data 106,
117, 128, 134, 141, 91, 84, 63, 42. Also derive the worst case complexity and best case
complexity for the same.
20. Define master theorem and give an example.
21. Explain Quicksort algorithm with an example
22. Write the algorithm for Merge sort. Trace Merge sort algorithm for the following data A,
L, G, O, R, I, T, H, M. Also derive the worst case complexity, best case and average case
of Merge sort.
23. Explain the general Divide and Conquer recurrence.
24. Explain the Binary Search algorithm with an example and estimate its time complexity
25. Write a sorting algorithm that uses Divide and Conquer technique which divides the
problem size by considering value. Trace the same algorithm for the following data 10, 22,
12, 8, 41, 7, 5, 36, 2. Also derive the worst case complexity and best case complexity for
the same.
26. Define time complexity and space complexity of an algorithm.
27. Define an algorithm. Explain the characteristics of an algorithm with an example.
28. Write an algorithm for Tower of Hanoi problem and determine its time complexity
29. Define Asymptotic notations
30. If 𝑡1 (𝑛) ∈ 𝑂(𝑔1 (𝑛)) 𝑎𝑛𝑑 𝑡2 (𝑛) ∈ 𝑂(𝑔2 (𝑛)), prove that 𝑡1 (𝑛) + 𝑡2 (𝑛) ∈
𝑂(max{𝑔1 (𝑛), 𝑔2 (𝑛))
31. If M(n) denotes the number of moves in tower of Hanoi puzzle when n disks are
involved, give a recurrence relation for M(n) and solve this recurrence relation.
32. Solve the following recurrence relation
i) f(n) = f(n-1) + n , f(0) =0
ii) x(n) = 3x(n-1), x(1) = 4
iii) x(n) = x(n/2) + n, x(1) = 1
33. Assuming that n is a power of 2, solve the recurrence relation
T(n) = 2T(n/2) +2. Take T(2) = 1 and T(1) = 0.
T(n) = 2 T(n/2) + 1
T(n) = T(n/2) + n
34. With the help of flow chart, explain the various steps of algorithm design and analysis
process
35. Compare the order of growth of ½ n (n-1) and n2
36. Give an algorithm for linear search. If C(n) denotes the count of the basic operation of the
algorithm(n denotes input size), obtain an expression for C(n) and determine its order of
growth
37. Explain mathematical analysis of non-recursive algorithm with an example.
38. List and explain important problem types that are solved by computer.
39. Design an algorithm for checking whether all the elements in a given array are distinct or
not. Derive its time complexity
40. What are the steps involved in non-recursive analysis of an algorithm?
41. What is the importance of basic operation?
42. Write iterative and recursive algorithms for counting the number of binary digits of a
decimal number n. Derive its time complexity.
43. Compare the order of growth of the following functions using limits.
a)log2n and √n
b)n! and 2n
1
n (n − 1) and log 2 n .
2
44. Write algorithms for matrix multiplication and transpose of a matrix. Derive their time
complexities.
45. What are the steps involved in non-recursive analysis of an algorithm?
46. Explain the analysis framework for analyzing the efficiency of algorithms
47. Write a recursive Fibonacci algorithm and determine its time complexity.
48. Write an algorithm for finding the sum of squares of numbers from 1 to n.
Answer the following questions for the same:
• What does the algorithm compute?
• What is the basic operation?
• How many times is the basic operation executed?
• Mention the efficiency class of the algorithm
• Suggest an improvement for the same.
49. For the following algorithms indicate
(1) a natural size metric for the input
(2)its basic operation
(3)whether basic operation count can be different for inputs of the same size
Alg1: Computing sum of N nos
Alg2:Finding the largest in a given set of N numbers
Alg3:Computing factorial of N

50. Explain the basic efficiency classes.