4.1 Divide and Conquer

There are a number of general and powerful computational strategies that are repeatedly used in computer science. It is often possible to phrase any problem in terms of these general strategies. These general strategies are Divide and Conquer, Dynamic Programming. The techniques of Greedy Search, Backtracking and Branch and Bound evaluation are variations of dynamic programming idea. All these strategies and techniques are discussed in the subsequent chapters.

The most widely known and often used of these is the divide and conquer strategy. The basic idea of divide and conquer is to divide the original problem into two or more sub-problems which can be solved by the same technique. If it is possible to split the problem further into smaller and smaller sub-problems, a stage is reached where the sub-problems are small enough to be solved without further splitting. Combining the solutions of the individuals we get the final conquering. Combining need not mean, simply the union of individual solutions. Divide and Conquer involves four steps

1. Divide
2. Conquer [Initial Conquer occurred due to solving]
3. Combine
4. Conquer [Final Conquer].

In precise, forward journey is divide and backward journey is Conquer. A general binary divide and conquer algorithm is : Procedure D&C (P,Q) //the data size is from p to q { If size(P,Q) is small Then Solve(P,Q) Else M ¬ divide(P,Q) Combine (D&C(P,M), D&C(M+1,Q)) } Sometimes, this type of algorithm is known as control abstract algorithms as they give an abstract flow. This way of breaking down the problem has found wide application in sorting, selection and searching algorithm. 4.1 Binary Search: Algorithm: m¬ (p+q)/2 If (p £ m £ q) Then do the following Else Stop If (A(m) = Key Then ‘successful’ stop Else If (A(m) < key Then q=m-1; Else p¬ m+1 End Algorithm. Illustration : Consider the data set with elements {12,18,22,32,46,52,59,62,68}. First let us consider the simulation for successful cases. Successful cases: Key=12 P Q m Search 1 9 5 x 1 4 2 x 1 1 1 successful To search 12, 3 units of time is required   Key=18 P Q m Search 1 9 5 x 1 4 2 successful To search 18, 2 units of time is required Key=22 P Q m Search 1 9 5 x 1 4 2 x 3 4 3 successful To search 22, 3 units of time is required Key=32 P Q m Search 1 9 5 x 1 4 2 x 3 4 3 x 4 4 4 successful To search 32, 4 units of time is required Key=46 P Q m Search 1 9 5 successful To search 46, 1 unit of time is required Key=52 P Q m Search 1 9 5 x 6 9 7 x 6 6 6 successful To search 52, 3 units of time is required Key=59 P Q m Search 1 9 5 x 6 9 7 successful To search 59, 2 units of time is required Key=62 P Q m Search 1 9 5 x 6 9 7 x 8 9 8 successful To search 62, 3 units of time is required Key=68 P Q m Search 1 9 5 x 6 9 7 x 8 9 8 x 9 9 9 successful To search 68, 4 units of time is required   3+2+3+4+1+3+2+4 Successful average search time= ------------------------- 9 unsuccessful cases Key=25 P Q m Search 1 9 5 x 1 4 2 x 3 4 3 x 4 4 4 x To search 25, 4 units of time is required       Key=65 P Q m Search 1 9 5 x 6 9 7 x 8 9 8 x 9 9 9 x To search 65, 4 units of time is required 4+4 Unsuccessful search time =-------------------- 2 average (sum of unsuccessful search time search = + sum of Successful search time)/(n+(n+1)) time
Clik here for more details:
http://www.vyomworld.com/gate/cs/ada/4.1.asp