Design and Analysis of Algorithms · Unit 3 · 8 hrs
Divide and Conquer Algorithms
Exam-focused notes for Divide and Conquer Algorithms (Design and Analysis of Algorithms, CSC325): what the TU syllabus asks and how it has actually been tested, with 10 solved past questions from this unit.
What this unit covers
- Searching Algorithms: Binary Search, Min-Max Finding and their Analysis
- Sorting Algorithms: Merge Sort and Analysis, Quick Sort and Analysis (Best Case, Worst Case and Average Case), Heap Sort (Heapify, Build Heap and Heap Sort Algorithms and their Analysis), Randomized Quick sort and its Analysis
- Order Statistics: Selection in Expected Linear Time, Selection in Worst Case Linear Time and their Analysis
Order Statistics
What is order statistics? Write and analyze the algorithm for randomized quick sort.[10]
--- Definition: The i-th order statistic of a set of n elements is the i-th smallest element in the set. In other words, if we sort the elements in ascending order, the element at position i is the i-th order statistic. Special Cases: - 1st order statistic ...
Full solved answer →Divide and Conquer Strategy and Worst-Case Linear Time Selection Algorithm
--- A divide and conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to...
Full solved answer →Searching Algorithms
Justify the worst case for binary search. Find the edit distance from the string "RELEVANT" to "ELEPHANT" using dynamic programming approach. [5+0]
Binary search operates on a sorted array. It compares the target with the middle element. If they are unequal, half the array is discarded, and the process repeats on the remaining half. $$T(n) = T\left(\frac{n}{2}\right) + O(1), \quad T(1) = O(1)$$ The wor...
Full solved answer →Write down nimmax algorithm and analyze its complexity. [5]
--- The Minimax algorithm is a recursive backtracking algorithm used in two-player zero-sum games (e.g., Chess, Tic-Tac-Toe). It determines the optimal move for a player assuming the opponent also plays optimally. - The MAX player tries to maximize the scor...
Full solved answer →Sorting Algorithms
What is the worst case of quick sort and how does randomize quick sort handle this problem? Sort the data ${-2, 4, -3, 6, 12, 10, 11, 13, 9}$ using quick sort. [10]
- Array to sort: $\{-2, 4, -3, 6, 12, 10, 11, 13, 9\}$ - Number of elements: $n = 9$ - Marks: 10 --- Quick Sort selects a pivot and partitions the array into elements smaller and larger than the pivot, then recursively sorts each part. Worst case occurs whe...
Full solved answer →Discuss heapify operation with example. Write down its algorithm and analyze its time and space complexity.[10]
--- A heap is a complete binary tree stored as an array where: - Max-Heap property: Every parent node is greater than or equal to its children. - Min-Heap property: Every parent node is less than or equal to its children. For an array A with 0-based indexin...
Full solved answer →Trace the quick sort algorithm for sorting the array $A[] = {15, 7, 6, 23, 18, 34, 25}$ and write its best and worst complexity. [5]
- Array to sort: $A[] = \{15, 7, 6, 23, 18, 34, 25\}$, indices $0$ to $6$ - $n = 7$ elements - Required: trace Quick Sort, and best and worst case time complexity - Pivot rule not specified. I use the first element as pivot (standard TU convention, Lomuto/H...
Full solved answer →Explain about the divide and conquer paradigm for algorithm design with suitable example. Write the Quick sort algorithm using randomized approach and explain its time complexity.[10]
--- Divide and Conquer is an algorithm design paradigm that solves a problem by: 1. Divide: Breaking the original problem into a number of smaller subproblems that are similar to the original problem. 2. Conquer: Solving the subproblems recursively. If the ...
Full solved answer →Explain the divide and conquer paradigm from algorithm design with a suitable example. Write the Quick sort algorithm using a randomized approach and explain its time complexity.[10]
--- Divide and Conquer is a fundamental algorithm design paradigm that solves a problem by breaking it into smaller subproblems, solving each subproblem recursively, and then combining the results to produce the final solution. Step Description ------------...
Full solved answer →Trace heap sort algorithm for the following data: (2, 9, 3, 12, 15, 8, 11) [5]
- Array (0-indexed): $A = [2, 9, 3, 12, 15, 8, 11]$, size $n = 7$ - Sort in ascending order using Max-Heap. Index relations: left child $= 2i+1$, right child $= 2i+2$. --- Last non-leaf node $= \lfloor n/2 \rfloor - 1 = 2$. Heapify from index 2 down to 0. H...
Full solved answer →Make Unit 3 stick
Practice CSC325 with flashcards & quizzes