Divide and Conquer

Merge Sort: Divide an array into two halves, recursively sort each half, and then merge the sorted halves to obtain the final sorted array.

Quick Sort: Choose a pivot element, partition the array into elements greater than and less than the pivot, and recursively sort the partitions.

Binary Search: Divide a sorted array in half and eliminate one half based on the comparison with the target element.

Closest Pair of Points: Find the closest pair of points among a set of points in a plane.

Strassen's Matrix Multiplication: Multiply two matrices using a divide and conquer approach to reduce the number of scalar multiplications.

A strategy in algorithm design that involves breaking down a complex problem into smaller subproblems, solving these subproblems independently, and then combining their solutions to obtain the solution to the original problem. 

This approach is particularly useful for solving problems with overlapping subproblems and can lead to efficient solutions for a wide range of problems.

The central idea of the divide and conquer algorithm is to divide a problem into smaller subproblems that are similar to the original problem but simpler to solve. 

Once the subproblems are solved, their solutions are combined to solve the larger problem.

Divide: Break the problem down into smaller subproblems that are structurally similar to the original problem.

Conquer: Solve the subproblems recursively. If the subproblems are small enough, solve them directly.

Combine: Combine the solutions of the subproblems to obtain the solution to the original problem.

Advantages: Divide and conquer often leads to elegant and efficient solutions, especially for problems with recursive structures.

Disadvantages: There can be overhead associated with recursion and combining subproblem solutions. It might not be suitable for problems that don't naturally divide into subproblems or where the combination step is complex.