| 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
- Divide
- Conquer [Initial Conquer occurred due to solving]
- Combine
- 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
Study Notes Home | Next Section>>
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
- Divide
- Conquer [Initial Conquer occurred due to solving]
- Combine
- 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
|
