The Divide and Conquer, Generalization Approach to Solving Problems
"Everything should be made as simple as possible, but not simpler" Albert Einstein
In these problem solving article series, we deliberately started exploring the brute force approach first, because it feels more natural, to myself at least, that we at least go through a mental map of a proposed solution.
Most of the times than not, we will find out that we can actually refine a brute force solution iteratively for better and better solutions.
One of the most important approaches in solving problems that has been proven to work not just in computer science, but also in other fields including politics and sociology, and indeed in other applied areas, is the divide and conquer approach.
In this approach, for any given problem, we ask ourselves a question: Can we divide our problem into two or more independent sub problems and thereby solve the original problem using the solutions to the sub-problems?
Independent sub-problems emphasized here for a reason...keep on the look out for my consecutive article discussion about recursion and dynamic programming, in which we will try and address some confusion between these two approaches, but for now let's concentrate of our main subject: divide and conquer...
The divide-and-conquer approach to solving a problems is actually a three step process:
- Breaking a problem into sub-problems that are themselves smaller instances of the same type of problem.
- Recursively solving the sub-problems
- Appropriately combining the solutions to the sub-problems,
Put in a bit more succinct way:
Divide → Conquer → Merge
Some of the most common algorithms that make use of the divide and conquer approach include:
- Quick Sort
Quick sort algorithm also called partition-exchange sort is an O(n log n) efficient sorting algorithm in it's best case and average case scenario, but can have a worst case O(n2) performance, serving as a systematic method for placing the elements of an array in order.
We will dive deeper into the quick sort algorithm in a separate article later in the series but briefly quick sort picks a pivot element, rearranges the array elements in such a way that all elements smaller than the picked pivot element move to left side of pivot, and all greater elements move to right side. Finally, the algorithm recursively sorts the sub-arrays on left and right of pivot element.
- Merge Sort
Merge Sort is a comparison based sorting algorithm, in which we cut an array in half over and over again until each piece is only 1 item long. Then those items are put back together (merged) in sort-order .
This article is about divide-and-conquer algorithms, which merge sort makes use of, but merge sort deserves an article of its own that we will tackle later.
- Binary Search
Binary search is a searching algorithm that uses the divide-and-conquer concept, in which on each step, the algorithm compares the input element x with the value of the middle element in an array. If the values match, it returns the index of middle. Otherwise, if x is less than the middle element, then the algorithm recurs for left side of middle element, else it recurs for right side of middle element.
We will discuss binary search in a separate article on binary search.
- Strassen's Matrix Multiplication
Strassen's algorithm is an efficient algorithm to multiply two matrices. A simple method to multiply two matrices needs 3 nested loops and is O(n^3). Strassen’s algorithm is more efficient such that it multiplies two matrices in O(n^2.8974) time and is useful in practice for large matrices, but would be slower than the fastest known algorithms for extremely large matrices
We will look at Strassen's algorithm in a separate article.
Case Study: Triomino Puzzle
Problem Definition : A triomino is formed by joining three unit-sized squares in an L-shape. A mutilated chessboard (hereinafter referred to as an 8 x 8 Mboard) is made up of 64 unit-sized squares arranged in an 8 x 8 square, minus one square represented as a black square in the board below. Suppose that we are asked to design an algorithm which computes a placement of 21 triominos that covers the 8 x 8 MBoard.
Since there are 63 squares in the 8 x 8 Mboard and we have 21 triominos, a valid placement cannot have overlapping triominos, or triominos that extend out of the 8 x 8 MBoard.
Our triominos should therefore fit perfectly as demonstrated in the figure that it is possible to have a perfect fit.
How do we approach this problem starting with a blank 8 x 8 board?
It can be overwhelming to look at the whole 8x8 board at once let alone a 16 x 16 board, so let's try to divide and conquer our problem!
Let's 'divide' the 8x8 board into 4x4 boards as follows:
We must keep in mind that we are looking to place 21 triominos, and 1 triomino on its own having 2 squares on the longer side, and if we ask ourselves a question whether we can only have 1 triomino within the resultant 4 x 4 board, the answer is no. So let's 'divide and try to conquer' further into 2 x 2 boards:
If we ask ourselves again whether we can have only 1 triomino in the resultant 2 x 2 boards, our answer is yes. Should we split the 2 x 2 boards further? No, because it will not make sense, as our triomino with 2 squares on one side will not fit into 1 square, therefore the 2 x 2 squares are our 'atomic' sub-problem. "Everything should be made as simple as possible but not simpler" will apply here
Notice how simple our problem has become. We can then begin combining the squares back, but we will not do that manually.
Back to our problem definition...We can hypothesize that if a placement exists for an n x n MBoard, then one also exists for a 2n x 2n Mboard. We can take 4 n x n Mboards and arrange them to form a 2n x 2n square in such a way that three of the MBoards have their missing square set towards the centre. The gap in the centre can be covered with a triomino and, by hypothesis we can cover the 4 n x n MBoards with triominos as well.
Therefore a placement exists for any n that is a power of 2, and in particular, a placement exists for the 2^3 x 2^3 (in other words 8 x 8) MBoard , quod erat demonstrandum (Q.E.D).
Notice that the problem we were solving demonstrates divide and conquer as well as generalization...from 8x8 to 2^n x 2^n.
Happy problem solving until the next post...