Divide and Conquer
Friday, November 10, 20171 mins read
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:
- Divide and Conquer algorithm - Wikipedia
- Introduction to algorithms / Thomas H. Cormen . . . [et al.].—3rd ed.