Design & Analysis of Algorithm
(** Please go through the textbook Once. **)
Q1. Explain with diagram the general method of divide and conquer and also
mention the general recurrence relation
Sol:
Explanation:
● Divide: Break the big problem into smaller parts.
● Conquer: Solve the smaller parts (usually by recursion).
● Combine: Join the results of the smaller parts to get the final answer.
Q2. Apply the logic of the Josephus problem to determine the survivor for a given
'n' and 'k' 7 and 3.
Sol:
Q3. Apply the Source Removal method to perform topological sorting on a given
directed acyclic graph.
Sol:
Q4. Develop a divide and conquer approach to solve the Max-Min problem for a
given set of numbers. 25,63,13,78,19,62
Sol:
Q5. Demonstrate the steps involved in solving the Johnson-Trotter problem for a
small value of 'n'.
Sol:
Step 1: Initialize
Start with 1 2 3, all directions pointing left (←).
Step 2: Find the largest mobile integer
An integer is mobile if it is greater than the number it’s pointing to.
Step 3: Swap it
Swap the mobile number with the one in the direction it's pointing.
Step 4: Reverse directions
All numbers greater than the moved number will reverse their directions.
Repeat steps 2–4 until no mobile number remains.
Q6. Describe mathematical techniques to analyze the time complexity of a given
recursive algorithm.
Sol:
1. Substitution Method (Iteration/Expansion Method)
● Expand the recurrence step by step until a pattern emerges.
● Useful for deriving closed-form solutions.
Eg:
Final answer: T(n) = O(n)
2. Recursion Tree Method
● Visualize recursive calls as a tree.
● Calculate work done at each level and sum it.
Eg:
T(n)=2T(n/2)+n
3. Master Theorem
Used for divide-and-conquer recurrences of the form:
Q7. Illustrate the quick sort algorithm and analyze it.
Sol:
Q8. Apply Johnson Trotter algorithm for n=1 2 3
Sol:
Q9. Illustrate the Depth-First Search (DFS) based approach for topological sorting.
Sol:
Q10. Illustrate the merge sort algorithm and analyze it.
Sol:
Q11. Apply the Master Theorem to find the asymptotic solution for a given
recurrence relation. T(n)=8T(n/3)+5n
Sol:
Q12. Describe the general method employed by the Divide and Conquer paradigm.
Sol: Same as Q1
Q13. Illustrate the Merge Sort algorithm by tracing its execution on an unsorted
array. 19,56,72,28,56,47,9
Sol:
Q14. Explain the core principle of the Decrease and Conquer strategy.
Sol:
● Solve the problem by reducing it to a smaller instance of the same problem.
● Usually, reduce the input size by a constant amount (commonly by 1).
● Solve the smaller instance recursively or iteratively.
● Use the solution of the smaller problem to build the solution to the original
problem.
● This continues until a base case is reached that is easy to solve.
● It is simpler than Divide and Conquer because it handles only one
subproblem at each step.
Q15. Develop the Binary Search algorithm to locate a specific element in a sorted
array.
Sol: Same as Q19
Q16. State and explain Master's Theorem.
Sol: Used to determine the time complexity of divide-and-conquer recursive
algorithms of the form:
Where:
● a ≥ 1: number of subproblems
● b > 1: factor by which the problem size reduces
● f(n): cost of dividing and combining subproblems
Q17. Explain the divide and conquer strategy with an example.
Sol: Same as Q1
Eg: Same as Q13
Q18. Compare the performance of merge sort and quick sort algorithms.
Sol:
Merge Sort
● Always divides an array into two equal parts.
● Time complexity: O(n log n) in all cases.
● Uses extra space (O(n)).
● Stable sort (maintains order of equal elements).
● Good for linked lists and large datasets.
● Slower in practice due to merging overhead.
Quick Sort
● Divides array using a pivot element.
● Time complexity:
○ Best/Average: O(n log n)
○ Worst: O(n²) (bad pivot choice)
● In-place sorting (no extra space needed).
● Not stable by default.
● Faster in practice on arrays with good pivot strategy.
● Performance depends on pivot selection.
Q19. Design an algorithm for binary search and analyze its time complexity.
Sol:
Q20. Analyze the role of recurrence relations in algorithm analysis.
Sol:
● Recurrence relations express the time complexity of recursive algorithms.
● They describe the total time based on the time spent on smaller subproblems.
● Help in understanding how the algorithm scales with input size.
● Commonly used to analyze Divide and Conquer algorithms like Merge Sort,
Quick Sort, etc.
● Example: Merge Sort → T(n) = 2T(n/2) + O(n)
● Solving the recurrence gives exact or asymptotic time complexity.
● Methods to solve: Substitution, Recursion Tree, Master’s Theorem.