DnC Strategy

In the section of Divide-and-Conquer overview, three steps in DnC procedures are discussed. Here in this module, more in-depth discussions will be covered in order to wrap up DnC topic.

DnC Implications

Although the high-level idea of DnC is essential in resolving many computation problems, it is worth noted that intuitively meaningful algorithm abstraction in DnC pattern in some scenarios are yet worse than the common way methods. (e.g. simply apply DnC in matrix multiplication does not help improve running time but make it more complex to comprehend.)

In general, the DnC problems are large enough to be divided into sub-problems defines a recursive-base, when the sub-problems are small enough to stop recursive calls, a base-case is defined.

Recurrence relations are a series of equations or inequalities to describe functions in terms of its smaller inputs. Solving the recurrence relations will be the key to unravel the computation complexity of DnC problems.

There are three ways to approach recurrence relations:

1. substitution method, a bound is guess and proven by mathematical induction.

2. recursion-tree method, recurrences are interpreted as a tree and solved by bounding summations.

3. master-method, a mathematical generalized form is given for most of the recurrences, and the most important idea to cover than the other two.

Note: master-method is only effective when the original problem gets split into sub-problems with equal size. If sub-problems differ in size, the recursion-method should be used instead.

DnC Examples

There are many divide-and-conquer paradigms in a vast amount of computation tasks. DnC principle is helpful yet imperfect to provide a best algorithm pattern at all-time.

Merge Sort

As a widely adopted algorithm across various application systems, Merge Sort is simple to evaluate given its identity of a divide-and-conquer algorithm.

For many beginners of divide-and-conquer paradigm, Merge Sort is a good start.

Counting Inversions

A pair of keys with random arrangement got compared with the in-order keys to output the number of inversions between the two, called the task of counting inversions. Mathematically speaking, more the difference value between two arrays, more lower the ranking comparisons. It is a widely used algorithm across various subjects such as voting theory, collaborative filtering etc.

The general idea is to recursively compute the similarities of two arrays from index і to index ј accordingly against the left n/2 (і,ј < n/2) of them and the right n/2 (і,ј > n/2) of them. Upon completion of subroutines above, compute the similarities against the whole length (і < n/2 < ј) and sum all the returned results.

Matrix Multiplication

A novel method Strassen's Algorithm magically improves the matrix multiplication by adoption of DnC pattern. It counters the naive matrix splitting method which fails to decrease the running time on average.

Quick Sort

Though choosing a pivot in each sub-problem is the major task in Quick Sort algorithm, it utilizes divide-and-conquer in resolving sorting in partitions created in each run.

Its average-case running time Ο(n ⋅ log(n)) maintains the comparison-based sorting lower bound and Quick Sort is a good beginning for randomization techniques.