Introduction To
Divide and conquer is an algorithm design paradigm based on multi-branched recursion. A divide-and-conquer algorithm works by recursively breaking 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 the original problem.
This divide-and-conquer technique is the basis of efficient algorithms for all kinds of problems, such as sorting, finding the closest pair of points, syntactic analysis, and computing the discrete Fourier transform (FFT).
Understanding and designing divide-and-conquer algorithms is a complex skill that requires a good understanding of the nature of the underlying problem to be solved. As when proving a theorem by induction, it is often necessary to replace the original problem with a more general or complicated problem in order to initialize the recursion, and there is no systematic method for finding the proper generalization.
The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving recurrence relations.
Course Structure
Standard Algorithms
- Divide and Conquer Algorithm | Introduction
- Tiling Problem using Divide and Conquer algorithm
- Write a program to calculate pow(x,n)
- Divide and Conquer | Set 5 (Strassen’s Matrix Multiplication)
- The Skyline Problem using Divide and Conquer algorithm
- Maximum Subarray Sum using Divide and Conquer algorithm
- Longest Common Prefix using Divide and Conquer Algorithm
- Search in a Row-wise and Column-wise Sorted 2D Array using Divide and Conquer algorithm
- Karatsuba algorithm for fast multiplication using Divide and Conquer algorithm
- Distinct elements in subarray using Mo’s Algorithm
Binary Search Based
- Find closest number in array
- Check for Majority Element in a sorted array
- K-th Element of Two Sorted Arrays
- Find the Rotation Count in Rotated Sorted array
- Find the only repeating element in a sorted array of size n
- Find index of an extra element present in one sorted array
- Decrease and Conquer
- Binary Search using pthread
- Binary Search on Singly Linked List
- The painter’s partition problem | Set 2
- Find the number of zeroes
- Numbers whose factorials end with n zeros
- Find the missing number in Arithmetic Progression
- Number of days after which tank will become empty
- Find bitonic point in given bitonic sequence
Misc
- Iterative Tower of Hanoi
- Program for Tower of Hanoi
- Find cubic root of a number
- Allocate minimum number of pages
- Collect all coins in minimum number of steps
- Find a peak element in a 2D array
- Program to count number of set bits in an (big) array
- Find frequency of each element in a limited range array in less than O(n) time
- Minimum difference between adjacent elements of array which contain elements from each row of a matrix
- Search element in a sorted matrix
- Easy way to remember Strassen’s Matrix Equation
- Largest Rectangular Area in a Histogram | Set 1
- Advanced master theorem for divide and conquer recurrences
- Place k elements such that minimum distance is maximized
- Iterative Fast Fourier Transformation for polynomial multiplication
- Write you own Power without using multiplication(*) and division(/) operators
- Shuffle 2n integers in format {a1, b1, a2, b2, a3, b3, ……, an, bn} without using extra space