DESIGN AND ANALYSIS OF ALGORITHM (KECZ603)
Section-wise Detailed Answers
SECTION A
(Attempt all questions – Detailed explanations)
(a) Why is Heapify called only on the first half of elements while building a heap?
While building a heap from an array, the heap property needs to be enforced only on non-leaf nodes. In an array representation of a complete binary tree, all elements from index ⌊n/2⌋ + 1 to n are leaf nodes. Leaf nodes already satisfy the heap property because they do not have children.
Heapify is a procedure that compares a node with its children and fixes violations of the heap property. Since leaf nodes have no children, calling Heapify on them is unnecessary and wasteful. Therefore, Heapify is applied only from index ⌊n/2⌋ down to index 1 (or 0 in 0-based indexing). This optimization reduces unnecessary operations and ensures the heap is built efficiently in O(n) time.
(b) Recurrence relation of Tower of Hanoi and its solution
The Tower of Hanoi problem involves moving n disks from a source peg to a destination peg using an auxiliary peg, following the rule that no larger disk can be placed on a smaller one.
To move n disks:
Move n−1 disks from source to auxiliary peg.
Move the largest disk directly to the destination peg.
Move the n−1 disks from auxiliary peg to destination peg.
This leads to the recurrence relation:
T(n) = 2T(n−1) + 1, with T(1) = 1
Solving this recurrence using substitution:
T(n) = 2(2T(n−2) + 1) + 1
T(n) = 4T(n−2) + 3
Continuing this expansion gives:
T(n) = 2ⁿ − 1
Thus, the time complexity of Tower of Hanoi is exponential, O(2ⁿ), making it impractical for large values of n.
(c) Properties of Binomial Trees
A binomial tree of order k, denoted as Bₖ, has specific structural properties. It contains exactly 2ᵏ nodes and has a height of k. The root of the binomial tree has k children, which themselves are roots of binomial trees of orders k−1, k−2, ..., 0.
Each binomial tree is defined recursively and has the property that the number of nodes at depth d is equal to C(k, d). These properties make binomial trees suitable for implementing binomial heaps, which support efficient merging operations.
(d) Proof that a Red-Black tree with n internal nodes has height at most 2log(n+1)
A Red-Black tree is a balanced binary search tree with specific coloring properties. One crucial rule is that no two red nodes can be adjacent, meaning every red node must have black children.
Let bh be the black height of the tree. The minimum number of nodes in a Red-Black tree with black height bh is at least 2ᵇʰ − 1. Since the height h of the tree is at most twice the black height (because red nodes can only appear between black nodes), we have:
h ≤ 2bh
Since n ≥ 2ᵇʰ − 1
⇒ bh ≤ log(n + 1)
Therefore:
h ≤ 2log(n + 1)
This proves that Red-Black trees are height-balanced and guarantee logarithmic time operations.
(e) Why a shortest path cannot contain a cycle
A shortest path between two vertices must be the path with minimum total weight. If a path contains a cycle, it means that some vertices are revisited.
If the cycle has positive weight, removing it will reduce the total path cost, contradicting the assumption that the path was shortest. If the cycle has zero weight, removing it keeps the cost the same but simplifies the path. If the cycle has negative weight, the path can be reduced indefinitely, meaning no shortest path exists.
Hence, a shortest path never contains a cycle.
(f) Difference between adjacency list and adjacency matrix
An adjacency matrix represents a graph using a two-dimensional array where rows and columns represent vertices. It allows fast edge lookup but consumes O(V²) space, making it inefficient for sparse graphs.
An adjacency list stores each vertex along with a list of its adjacent vertices. It uses O(V + E) space and is efficient for sparse graphs. Traversal is also faster in adjacency lists for most graph algorithms.
(g) Branch and Bound technique
Branch and Bound is an optimization technique used to solve combinatorial problems. It systematically explores solution spaces by branching into subproblems and uses bounds to eliminate subproblems that cannot produce better solutions than the current best.
This method significantly reduces computation compared to brute force. It is commonly applied in problems like the Traveling Salesman Problem and Knapsack Problem.
(h) Dynamic Programming vs Divide and Conquer
Divide and Conquer breaks a problem into independent subproblems, solves them recursively, and combines results. Subproblems do not overlap, as seen in merge sort.
Dynamic Programming is used when subproblems overlap. It stores intermediate results to avoid recomputation, improving efficiency. Examples include Fibonacci, LCS, and Matrix Chain Multiplication.
(i) Complexity of naïve string matching algorithm
The naïve string matching algorithm compares a pattern of length m with a text of length n by shifting the pattern one position at a time.
In the worst case, it performs m comparisons for each of the n−m+1 shifts, resulting in a time complexity of O(nm).
(j) Difference between NP-Hard and NP-Complete
NP-Hard problems are at least as hard as the hardest problems in NP but may not belong to NP. NP-Complete problems are both in NP and NP-Hard.
Every NP-Complete problem can be verified in polynomial time, while NP-Hard problems may not have verifiable solutions in polynomial time.
SECTION B
(Attempt any three – Detailed solutions)
(a) Counting Sort on array {2,0,2,3,5,7,6,3,0,2,1,3}
Counting sort works by counting occurrences of each element. First, an auxiliary array C is created to store frequencies. The maximum element is 7, so C has indices 0 to 7.
After counting frequencies, cumulative counts are computed. Then the output array is built by placing elements in their correct positions using cumulative counts.
This algorithm runs in O(n + k) time and is stable, making it efficient for integers in a limited range.
(c) Minimum Cost Spanning Tree and Prim’s Algorithm
A Minimum Cost Spanning Tree (MST) connects all vertices of a graph with minimum total edge weight and no cycles.
Prim’s algorithm starts from an arbitrary vertex and repeatedly adds the minimum-weight edge that connects a vertex in the tree to a vertex outside it. This process continues until all vertices are included.
Using a priority queue, Prim’s algorithm runs in O(E log V) time.
(e) Approximation Algorithm and Vertex Cover
An approximation algorithm produces solutions close to optimal within a known factor. A P(n) approximation algorithm guarantees a solution within P(n) times the optimal.
For the vertex cover problem, a 2-approximation algorithm repeatedly selects an edge and includes both its endpoints in the cover. This guarantees the solution is at most twice the optimal size.
SECTION C
(Attempt any one – Detailed explanation)
(a) Merge Sort Algorithm and Time Complexity
Merge sort follows the divide and conquer approach. It divides the array into halves until single-element arrays are obtained. Then, it merges these arrays in sorted order.
The recurrence relation is:
T(n) = 2T(n/2) + O(n)
Using the Master Theorem, the time complexity is O(n log n) in all cases. Merge sort is stable and efficient but requires additional memory.
(b) Quick Sort with Example
Quick sort selects a pivot, partitions the array around the pivot, and recursively sorts subarrays.
Applying quick sort to:
12, 13, 10, 5, 7, 3, 2, 17, 23, 16
After successive partitions, the sorted order becomes:
2, 3, 5, 7, 10, 12, 13, 16, 17, 23
The average time complexity is O(n log n), but the worst case is O(n²). Proper pivot selection reduces the likelihood of worst-case behavior.
