DIVIDE & CONQUER

DIVIDE & CONQUER

Definition:

Divide & conquer is a general algorithm design strategy with a general plan as follows:

1. DIVIDE:

A problem’s instance is divided into several smaller instances of the same problem, ideally of about the same size.

2. RECUR:

Solve the sub-problem recursively.

3. CONQUER:

If necessary, the solutions obtained for the smaller instances are combined to get a solution to the original instance.

Diagram 1 shows the general divide & conquer plan

NOTE:

The base case for the recursion is sub-problem of constant size.

Advantages of Divide & Conquer technique:

• For solving conceptually difficult problems like Tower Of Hanoi, divide & conquer is a powerful tool

• Results in efficient algorithms

• Divide & Conquer algorithms are adapted foe execution in multi-processor machines

• Results in algorithms that use memory cache efficiently.

Limitations of divide & conquer technique:

• Recursion is slow

• Very simple problem may be more complicated than an iterative approach.

Example: adding n numbers etc

General divide & conquer recurrence:

An instance of size n can be divided into b instances of size n/b, with “a” of them needing

to be solved. [ a ≥ 1, b > 1].

Assume size n is a power of b. The recurrence for the running time T(n) is as follows:

 

T(n) = aT(n/b) + f(n)

where:

f(n) – a function that accounts for the time spent on dividing the problem into smaller ones and on combining their solutions

Therefore, the order of growth of T(n) depends on the values of the constants a & b and the order of growth of the function f(n).

Master theorem

Definition:

Merge sort is a sort algorithm that splits the items to be sorted into two groups, recursively sorts each group, and merges them into a final sorted sequence.

Features:

• Is a comparison based algorithm

• Is a stable algorithm

• Is a perfect example of divide & conquer algorithm design strategy

• It was invented by John Von Neumann

Algorithm:

ALGORITHM Mergesort ( A[0… n-1] )

//sorts array A by recursive mergesort

//i/p: array A

//o/p: sorted array A in ascending order

if n > 1

copy A[0… (n/2 -1)] to B[0… (n/2 -1)]

copy A[n/2… n -1)] to C[0… (n/2 -1)]

Mergesort ( B[0… (n/2 -1)] )

Mergesort ( C[0… (n/2 -1)] )

Merge ( B, C, A )

ALGORITHM Merge ( B[0… p-1], C[0… q-1], A[0… p+q-1] )

//merges two sorted arrays into one sorted array

//i/p: arrays B, C, both sorted

//o/p: Sorted array A of elements from B & C

Example:

Apply merge sort for the following list of elements: 6, 3, 7, 8, 2, 4, 5, 1

Solution:

Analysis:

• Input size: Array size, n

• Basic operation: key comparison

• Best, worst, average case exists:

Worst case: During key comparison, neither of the two arrays becomes empty before the other one contains just one element.

• Let C(n) denotes the number of times basic operation is executed. Then

Advantages:

• Number of comparisons performed is nearly optimal.

• Mergesort will never degrade to O(n2)

• It can be applied to files of any size

Limitations:

• Uses O(n) additional memory.