Advanced Algorithm Solutions
a) What do you understand by stable sort? Name two stable sorting algorithms.
A stable sorting algorithm maintains the relative order of records with equal keys. That means if two
elements have the same key, they appear in the same order in the sorted output as they did in the input.
Examples of stable sorting algorithms:
1. Merge Sort
2. Bubble Sort (also Insertion Sort, Counting Sort, etc.)
b) What do you understand by in-place sorting algorithm?
An in-place sorting algorithm sorts the data without using extra memory proportional to the input size. It
uses only a constant amount of additional space (O(1)).
Examples: Quick Sort, Heap Sort, Insertion Sort.
c) Explain different techniques for analyzing the algorithm.
Analysis of algorithm means determining its efficiency in terms of time and space. The main techniques
are:
1. Worst-case Analysis: Maximum time for any input of size n.
2. Average-case Analysis: Expected time over all possible inputs.
3. Best-case Analysis: Minimum time for favorable input.
4. Amortized Analysis: Average time per operation over a sequence of operations.
d) Give the recurrence relation for Merge Sort algorithm and explain its time complexity.
For Merge Sort:
T(n) = 2T(n/2) + O(n)
Using Master Theorem ⇒ T(n) = O(n log n)
Space complexity: O(n)
e) What do you understand by frequency count?
Frequency count is a method of analyzing algorithms by counting the number of times basic operations
are executed. It helps estimate time complexity based on how frequently each step runs.
f) Explain the properties of Max Heap with example.
Max Heap is a complete binary tree where:
1. Every parent node is greater than or equal to its children.
2. The tree is filled from left to right.
Example: For array [50, 30, 40, 10, 20, 35, 25], the tree satisfies Max-Heap because each parent ≥ its
children.
g) Define principle of optimality.
Principle of Optimality states that an optimal solution to a problem contains optimal solutions to its
subproblems. Used in Dynamic Programming.
Example: In the Shortest Path Problem, if the shortest path from A to C passes through B, then the path
from A to B and B to C are also shortest individually.
--- SECTION – B ---
a) Prove that if n ≥ 1, then for any n-key B-Tree of height h and minimum degree t ≥ 2:
h ≤ log■((n+1)/2)
Explanation with formula and derivation shown above.
b) Identify time complexity for following recurrences:
(i) T(n) = T(n−1) + n = O(n²)
(ii) T(n) = 2T(n/2) + n² = Θ(n²)
c) Knapsack Problem using Greedy Approach (Fractional):
Maximum Profit = 115 units
d) Height of Red-Black Tree ≤ 2·log■(n+1)
Explanation with properties and derivation shown above.
e) Counting Sort on array [0,0,1,1,1,3,3,5,5,5,3,2,2]
Sorted Output: [0,0,1,1,1,2,2,3,3,3,5,5,5]
--- SECTION – C ---
a) Apply Quick Sort on {7,2,3,4,9,15,6,12,11,19,20}
Sorted Array: [2,3,4,6,7,9,11,12,15,19,20]
Worst-case: O(n²), Average: O(n log n)
b) Sorting in Linear Time:
Examples: Counting Sort, Radix Sort, Bucket Sort
Time Complexity: O(n) when k = O(n)
Worst Case Time Complexity Explanation:
It represents the upper bound time taken by an algorithm for input size n.
Examples:
Linear Search – O(n)
Binary Search – O(log n)
Quick Sort – O(n²)
Merge Sort – O(n log n)