Standard Problems that uses Divide and Conquer Algorithm

1. Merge Sort for Linked List:

Merge Sort can be adapted for linked lists. It follows the same divide-and-conquer approach, dividing the linked list into two halves, recursively sorting each half, and then merging them.

Algorithm Steps:

• If the list is empty or has one element, it is already sorted.
• Split the linked list into two halves.
• Recursively sort each half.
• Merge the sorted halves.

2. How to make Merge Sort to perform O(n) comparisons in best case?

Optimizing Merge Sort to perform O(n) comparisons in the best case involves detecting if the input is already sorted and skipping unnecessary merging steps.

Algorithm Steps:

• Check if the input is already sorted.
• If sorted, skip merging and return the sorted array.
• Otherwise, proceed with the standard Merge Sort algorithm.

3. Iterative Quick Sort:

An iterative version of QuickSort uses a stack to eliminate the need for recursion. It follows the same steps as the recursive version but utilizes a stack data structure.

Algorithm Steps:

• Create an empty stack and push the initial values onto it.
• Perform iterations until the stack is empty.
• Pop values from the stack, partition, and push the indices of the subarrays.

4. Quick Sort on Singly Linked List:

Adapting QuickSort for singly linked lists involves partitioning the list based on a pivot, similar to the array version.

Algorithm Steps:

• Select a pivot from the list.
• Partition the list around the pivot.
• Recursively apply QuickSort to the partitions.

5. Median of Two Sorted Arrays

Finding the median of two sorted arrays involves merging the arrays and finding the middle element.

Algorithm Steps:

• Merge the two sorted arrays.
• If the total length is odd, return the middle element.
• If the total length is even, return the average of the two middle elements.

6. Count Inversions in an Array Using Merge Sort

Counting inversions in an array involves determining the number of pairs of indices (i, j) such that i < j and array[i] > array[j].

Algorithm Steps:

• Apply Merge Sort while counting inversions during the merging step.
• Merge the two halves, counting inversions when elements from the second half are chosen.

7. Closest Pair of Points

The Closest Pair of Points problem involves finding the pair of points with the smallest Euclidean distance among a set of points.

Algorithm Steps:

• Sort the points by their x-coordinates.
• Recursively find the closest pairs in the left and right halves.
• Check for a closer pair that spans the two halves.

8. Strassen’s Matrix Multiplication

Strassen’s Matrix Multiplication is a divide-and-conquer algorithm for multiplying matrices more efficiently than the standard method.

Algorithm Steps:

• Split the input matrices into submatrices.
• Recursively compute seven products.
• Combine the products to form the result.

9. Sort a Nearly Sorted (or K Sorted) Array

Sorting a nearly sorted array involves efficiently sorting an array where each element is at most k positions away from its final sorted position.

Algorithm Steps:

• Create a min-heap of size k + 1.
• Insert the first k + 1 elements into the heap.
• Extract the minimum and insert the next element from the array.

10. Search in an Almost Sorted Array

Searching in an almost sorted array involves finding the position of an element in an array where each element is at most k positions away from its final sorted position.

Algorithm Steps:

• Use a modified binary search to find the element.
• Compare the element with adjacent elements within the range of k.

11. K-th Element of Two Sorted Arrays

Finding the k-th element in two sorted arrays involves comparing the medians of the two arrays and eliminating half of the elements.

Algorithm Steps:

• Compare the medians of the two arrays.
• Eliminate the half that cannot contain the k-th element.
• Repeat the process until the k-th element is found.

12. K’th Smallest/Largest Element in Unsorted Array

Finding the k-th smallest or largest element in an unsorted array involves using QuickSelect, a variation of QuickSort.

Algorithm Steps:

• Choose a pivot and partition the array.
• Recursively apply QuickSelect to the relevant partition.
• Adjust the value of k based on the partitioning.
• Time Complexity of Divide and Conquer Algorithm:

Those preparing for the GATE (Graduate Aptitude Test in Engineering) exam in 2024 face many algorithmic challenges. Among the various algorithmic paradigms, “Divide and Conquer” stands out as a powerful approach to problem-solving. In this comprehensive guide for the GATE Exam, Divide and Conquer, and its applications will be explored through a range of important topics. These notes aim to provide a solid foundation for mastering these concepts in preparation for the upcoming GATE exam.