# Divide and Conquer

Friday, November 10, 2017

Say you want to go to Harvard for your graduate studies in a year. But, the academic fee of $40,000 is intimidating. And, with every passing week, it’s getting worse. So, what do you do? Think like a computer scientist. Divide the big amount into smaller manageable amount. Say, you take an education loan of$20,000. Hoping ;) that you will be lucky enough to get scholarship of at least $5,000; still you are falling short of$5,000. Doing a little math, you can figure it out that you need to save approx. $416/month i.e.$96/week. Now, you can cut your monthly expenses to save some money. Even though it does not ensure your acceptance into Harvard, you’ll have a handsome amount of money in your bank account after a year.

What we just did was to break a problem into smaller subproblems and the solve them and finally by combining the solutions of the subproblems, we solved the original problem. This approach of problem-solving is known as Divide and Conquer.

The three main steps of divide and conquer algorithm paradigm are:

• Divide the problem into subproblems
• Conquer the subproblems by solving them recursively or directly.
• Combine the solutions to the subproblems into the solution to get the solution of the original problem.

## Algorithms using Divide and Conquer paradigm:

• Binary search for searching
• Quicksort and merge sort for sorting
• Karatsuba algorithm for multiplication of large numbers
• Strassen’s algorithm for matrix multiplication

So, next time you come across a problem; think like a computer scientist and don’t forget:

Many a drop make an ocean.

References:

1. Divide and Conquer algorithm - Wikipedia
2. Introduction to algorithms / Thomas H. Cormen . . . [et al.].—3rd ed.