Algorithms Design Methods: Divide and Conquer Method:

Algorithms Design Methods:
Divide and Conquer Method:
To solve a large problem using divide and conquer approach, it most divided it into number of smaller problems and solve each part, then combine these sub solutions to obtain the solution of the original problem. Often, the subproblems that generated are, simply, smaller instances of the original problem and may be solved using divide and conquer strategy recursively.
The divide and conquer strategy involves the following steps:
Divide an instance of a problem into two or more smaller instances.
Solve each of the smaller instances.
Combine (if necessary) the solutions to the smaller instances to obtain the solution to the original instance.
In some problems, there is no need to the step 3 above, such as in binary search problem, that because the solution is find the element that we at look for it. So that there is no need to combine the solutions.
The control abstraction for the divide and conquer method as following:
DandC (P)
Begin
if small (P) return S(P)
else
divide P into smaller instances P1, P2,…,Pk, k>1
apply DandC to each of these subproblems
return combine(DandC(P1), DandC(P2),…, DandC(Pk))
Endif
End

Time complexities of Divide and Conquer method
If the size of the problem p is n and the sizes of subproblems P1, P2,…,Pk are n1, n2, ….,nk respectively, then the time complexities for the divide and conquer strategy is described as follow:
T(n)={?(g(n) if n small@T(n_1 )+T(n_2 )+T(n_3 )+?+T(n_k )+F(n) otherwise)}
Where:
T(n) : is the execution time of DandC for any inputs with size n.
g(n) : the computing time of solving the small problem
F(n) : the time of dividing and combining the problem P to its subproblems.
Binary Search
One of the problems that solved using Divide and conquer strategy is Binary search problem, that locate for element k in a sorted list a[1..n].
The idea: to search about the element k in the a[low..high] list, we search about k in three sublist a[low..mid-1], a[mid..mid], a[mid+1..high]. by comparing k with a[mid] two of the sublist will be removed.
This can be solved using divide and conquer method as in the following algorithm:
BinaySearch (a( ), k, low, high)
Begin
if ( low > high) then return 0
else
mid= (low+high)/2
if ( k = a(mid)) then return mid
else if ( k < a(mid)) then
BinarySreach(a,k,low,mid-1)
else BinarySearch(a,k,mid+1,high)
endif
endif
endif
End
Algorithm analysis:
Space complexities: each activation for the function require seven words that a, low, high, k, mid, name of function and return address.
In 1st activation n+1/21, 2nd activation n+1/22,…., mth activation n+1/2m
The last comparison is stopped when n+1=2m
Log(n+1)=log2m , m=log(n+1)
Therefore, SBinarySearch(n)= ?(logn)
Time complexities: The time complexities for this algorithm can be described as following:
TBinarySearch (n)={?(T_BinarySearch (1) if n=1@T_BinarySearch (n/2)+c otherwise)}

TBinarySearch (n)= TBinarySearch (n/2)+c
= TBinarySearch (n/22)+c+c
= TBinarySearch (n/23)+3c
= TBinarySearch (n/2m)+mc
Suppose n = 2m , m= log2n
= TBinarySearch (1)+c log2n
TBinarySearch (n) = ?(log2n)
This the worst and average cases time complexities for the successful search of the binary search algorithm. While the best case is equal to ?(1) (Why?).
For example, the binary search decision tree when n=14 is described as following where :
Internal nodes (represent successful states)=14=n
External node (represent fail states)=15=n+1





Binary search decision tree when n=14
Notes:
The maximum number of comparisons for the successful search =4 comparisons, Ex: 7 11 13 12
The minimum number of comparisons for the successful search = 1 comparisons


H.W:
Write algorithm to find the maximum number in one dimension array using Divide and Conquer strategy?
Rewrite Binary search algorithm without recursion(using while)?
Design the Ternary Search algorithm, then find the time complexities for it? (this algorithm divide the array into five sublists using two divided positions as below:

mid1=n/3 mid2=2n/3