Lecture No.
: 1
3rd Stage Subject: Algorithms Design and
Lecture time: 8:30-12:30 AM Analysis II
Instructor: Dr. Farah Al-Shareefi Department of computer science
1. Algorithm Design Methods:
1.1. Divide-and-Conquer Method:
In the divide-and-conquer approach to solve a large problem, we divide
it into some number of smaller problems; solve each of these; and combine
these solutions to obtain the solution to the original problem. Often, the
generated sub-problems are simply smaller instances of the original problem
and may be solved using the divide-and-conquer strategy recursively. The
divide-and-conquer approach is a top-down approach. That is, the solution to a
top-level instance of a problem is obtained by going down and obtaining
solutions to smaller instances.
The divide-and-conquer design strategy involves the following steps:
1. Divide an instance of a problem into one or more smaller instances.
2. Conquer (solve) each of the smaller instances. Unless a smaller instance is
sufficiently small, use recursion to do this.
3. If necessary, combine the solutions to the smaller instances to obtain the
solution to the original instance.
The reason we say "if necessary" in Step 3 is that in algorithms such as
Binary Search the instance is reduced to just one smaller instance, so there is no
need to combine solutions.
The abstracted procedure for the divide-and-conquer method as follow:
Procedure DandC(p);
begin
If small (p) then solve (p);
Else begin
Divide p into smaller instance p1, p2, p3, …, pk,
Apply DandC to each of these subproblems;
Combine( DandC(p1), DandC(p2), DandC(p3), …, DandC(pk));
Department of Computer Sciences 1
College of Sciences for Women
Lecture No. : 1
3rd Stage Subject: Algorithms Design and
Lecture time: 8:30-12:30 AM Analysis II
Instructor: Dr. Farah Al-Shareefi Department of computer science
end;
end;
If the size of the problem p is n and the sizes of sub-problems p1, p2, p3, …, pk, are n1,
n2, n3, …, nk respectively, then the time complexity for the divide-and-conquer
strategy is described as follow:
g(n) if n small
T(n) =
T(n1) + T(n2) + T(n3) + … + T(nk) + f(n) otherwise
Where T(n) : is the execution time of DandC for any inputs with size n.
g(n): the computing time of response for small problem.
f(n): the time of dividing and/or combining the problem p to its sub-problems.
EXAMPLES:
1. Binary search:
To locate the element k in sorted list a[1..n]
a[p] a[q]
a[p .. m-1] a[m .. m] a[m+1..q]
a[p .. m-1] a[m .. m] a[m+1..q] k
The idea: To locate the element k in the a[p..q] we locate the k in three sub-list
a[p..m-1] , a[m..m], and a[m+1..q]. By comparing k with a[m] two of the sub-list
will be removed.
Department of Computer Sciences 2
College of Sciences for Women
Lecture No. : 1
3rd Stage Subject: Algorithms Design and
Lecture time: 8:30-12:30 AM Analysis II
Instructor: Dr. Farah Al-Shareefi Department of computer science
Here we design an algorithm for binary search by using divide-and-conquer
method.
Function BinSearch(var a:ElemList; p, q:integer; k: Key): integer;
var m: integer;
Begin
m := (p +q) div 2;
If p > q then
BinSearch:= 0;
Else if k = a[m] then BinSearch:= m
Else if k > a[m] then BinSearch:= BinSearch(a, m+1, q, k)
Else BinSearch:= BinSearch(a, p, m-1, k);
End;
Tracing of Algorithm:
Locate the values 101, -14, and 82 in the following sorted list
A[1..9] = ( -15, -6, 0, 7, 9, 23, 54, 82, 101)
Locations: 1 2 3 4 5 6 7 8 9
Department of Computer Sciences 3
College of Sciences for Women
Lecture No. : 1
3rd Stage Subject: Algorithms Design and
Lecture time: 8:30-12:30 AM Analysis II
Instructor: Dr. Farah Al-Shareefi Department of computer science
k = 101 k = -14 k = 82
P Q M P Q M p q M
1 9 5 1 9 5 1 9 5
6 9 7 1 4 2 6 9 7
8 9 8 1 1 1 8 9 8
9 9 9 2 1
Found Not Found Found
Algorithm Analysis:
1- Space complexity:
Each activation requires 7 spaces ( 4 bytes for a, 4 bytes for each p,q,m, return
address and BinSearch, and k)
1st activation 2nd activation 3th activation … mth activation
n+1/21 n+1/22 n+1/23 … n+1/2m
The last comparison is stopped when
n + 1 = 2m
log2 (n + 1) = log2 2m
m = log2 n
where n: the no. of comparisons, m: the no. of activations
SBinSearch (n) = Θ(log2 n )
SBinSearch (n) = 7 log2 n
2- Time complexity:
TBinSearch (1) if n =1
TBinSearch (n) =
TBinSearch (n / 2) + c otherwise
TBinSearch (n) = TBinSearch (n / 2) + c
Department of Computer Sciences 4
College of Sciences for Women
Lecture No. : 1
3rd Stage Subject: Algorithms Design and
Lecture time: 8:30-12:30 AM Analysis II
Instructor: Dr. Farah Al-Shareefi Department of computer science
= TBinSearch (n / 22) + 2c
= TBinSearch (n / 23) + 3c
= TBinSearch (n / 2m) + mc
Suppose n = 2m
m = log2 n
= TBinSearch (n / 2m) + mc
= TBinSearch (1) + c log2 n
TBinSearch (n) = Θ(log2 n )
This the worst case time complexity for the successful search of the
binary search algorithm, while the best case time complexity is equal to Θ(1).
Example: Draw the binary search decision tree for a list of 14 elements and then find:
1- The maximum, minimum, and average number of comparisons for the
successful search.
2- The average number of comparisons for the failure search.
7
11
3
1 5 9 13
10 12 14
2 4 6 8
binary search decision tree when n= 14
Internal node (represent successful state)
Department of Computer Sciences 5
College of Sciences for Women
Lecture No. : 1
3rd Stage Subject: Algorithms Design and
Lecture time: 8:30-12:30 AM Analysis II
Instructor: Dr. Farah Al-Shareefi Department of computer science
External node ( represent failure state)
The maximum number of comparisons for the successful search = 4 comparisons.
The minimum number of comparisons for the successful search = 1 comparison.
The average number of comparisons for the successful search
(1 * 0) + (2 * 1) + (4 * 2) + (7 * 3) 31
= = = 2.214 comparisons
1+2+4+7 14
The average number of comparisons for the failure search
(1 * 3) + (14 * 4) 59
= = = 3.933 comparisons
1 + 14 15
The abstract:
The successful searches The failure searches
Best case Average case Worst case Best case Average case Worst case
Θ(1) Θ(log2 n ) Θ(log2 n ) Θ(log2 n )
Department of Computer Sciences 6
College of Sciences for Women
