"Divide and conquer" technique for solving problems

Different problems imply the use of different techniques and algorithms for their solution. A necessary prerequisite for designing a solution is a detailed knowledge of the nature and the relevant problem. Under the assumption that this condition is met, the starting point for solving a problem through a particular algorithm is the modeling of that problem. By problem modeling or representation we refer to the representation of the problem through certain data structures. It is rare to use algorithms to find answers that aren't meant to be used with programming languages or other computer programs. This is also the reason why I will directly proceed with presentation as a data structure, namely the presentation as a digital data, and the purpose of this short article is to deal with the "Divide and Conquer" technique in this aspect.

A well-designed issue model has the benefit of accelerating the generation of solution ideas. The solution of the problem represents the target state of the problem. This is usually determined through some pattern or certain rules. The path to the solution has its own precisely defined steps and the corresponding technique also precisely defined. One of the most frequent techniques used by different algorithms is the "Divide and Conquer" technique. Based on the socio-political principle of fragmentation or division and ruling, the technique aims to divide a problem into parts of the same nature, offer a solution for these and finally unite them in the total solution. To illustrate this technique, the problem known as "Tromino Puzzle" and the "Merge sort" algorithm will be treated.

Tromino Puzzle presents a matrix of order 2n where n>0 which must be filled with "tromino" except for one field which must be left free. We can define the free field randomly. The following figure shows an example of what "tromino" represents and what a completed matrix looks like.

The desired state for this problem is a matrix which has only one cell unfilled, whose position as said can be chosen or generated randomly. Modeling this problem is somewhat intuitive. The graphical representation itself associates us with the representation through two-dimensional arrays or matrices. To apply the "Divide and Conquer" technique, we need to analyze what the base case is that we know about or can solve through base comparisons. The simplest case is the case when the matrix is of size 2x2. In that case, we check through the two loops in which position the free space is found, and in the others we place the "tromino".

To arrive at this basic case, we need to recursively divide the matrix into 4 sub-matrices (each quadrant a matrix in itself) until the rank of the matrix is 2x2, which represents the basic case (both for the algorithm and for recursion). During matrix partitioning, we check in which of the 4 sub-matrices the free space is found. Under the matrix which contains the free space remains as it is, while the others are connected through a "tromino". This happens until we get to the base case that was mentioned. From there, the matrix is completed recursively (now backwards). The following is presented with an illustrated example.

The first step - dividing into sub-matrices and connecting through "tromino" the sub-matrices where there is no free space

The second step – completing the basic cases

The third step – merging into a single solution

The pseudocode for the implementation of this algorithm looks like the following.

Tromino function(matrix, dimension)

- If the dimension is equal to 2

o Complete the base case

- Otherwise

o Divide the matrix into 4 sub matrices

o Check in which sub matrix the free space is located

o Connect to other matrices through a "tromino"

o For each sub matrix call the recursive function Tromino(sub matrix, new dimension)

- Merge sub matrices

- Return the result of concatenation of submatrices

Following these steps, or this strategy, guarantees us the completion of every valid matrix of any rank for the problem in question.

One of the most used algorithms for sorting, the "Merge sort" algorithm, is built based on the same technique. This algorithm is used for sorting of different strings. The pseudocode of this algorithm may sound a bit complicated so it is deliberately avoided in this article. However, it can be found in almost any book (including bibliography) that deals with the complexity and design of algorithms. The algorithm works in such a way that it splits the string in half recursively until it reaches two strings with one member each. From that step, they are sorted through the comparison of the elements of the left and right side, and then their union also in a recursive form, until the length of the initial string is completed. It is graphically illustrated below.

As a conclusion, it can be said that the technique "Divide and conquer" is a simple technique in implementation but very efficient and that finds application in a wide range of problems. Many popular algorithms (especially for sorting or sorting) use this technique in different variants in order to reduce the time complexity of executing the respective algorithms. Definitely a recommended technique in problems whose nature can be applied.

Bibiliography

Levitin A, Introduction to the design and analysis of algorithms – 3rd Edition, 2012, Pearson Education