DESIGN AND ANALYSIS OF
ALGORITHMS
Design and Analysis of
UNIT-II
Algorithms
DEVIDE AND CONQUER
From,
Ashwini Janagal
Associate Professor
Department of ISE,
JNN College of Engineering,
Shivamogga-577204,
Karnataka,
India.
General Method
If there is a function to compute on n
inputs the divide-and-conquer strategy
suggests splitting the inputs into k distinct
subsets,1< k < n, yielding k subproblem.
Solve ‘k’ Subproblems
Combine the sub-solutions
General Method
Subproblems are same as main problem
Divide until subproblems are small enogh to be
solved
General Method
Ex: Detecting a Couterfeit Coin in Bagful of coins.
Note:
1. Counterfeit coin weigh less than other coins.
2. Two weighing machines are given for you.
How do you proceed with job?
General Method
Ex: Detecting a Couterfeit Coin in Bagful of coins.
Note:
1. Counterfeit coin weigh less than other coins.
2. Two weighing machines are given for you.
Method 1:
Take two coins and weigh them. If they weigh different then the
one which weigh less is counterfeit.
Else, compare next two........and continue until you find
counterfeit or all the coins are compared.
General Method
Ex: Detecting a Couterfeit Coin in Bagful of coins.
Note:
1. Counterfeit coin weigh less than other coins.
2. Two weighing machines are given for you.
Method 2:
1. Suppose you have 100 coins, make 2 sets of 50each.
2. Weigh them, if they weigh same then there is no counterfeit coin.
3. Else, Take one with less weight and continue the process.
General Method
Problem
A B
B1 B2
B1a B1b
General Method
Algorithm DAndC(P)
{
if Small(P) then 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));
}
}
General Method
Computing Time is
𝑇 (𝑛)=
{ 𝑔( 𝑛) 𝑛 𝑠𝑚𝑎𝑙𝑙
𝑇 (𝑛 1)+ 𝑇 (𝑛 2)+......+𝑇 (𝑛 𝑘 )+ 𝑓 (𝑛) 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 }
is time to divide and combine.
a and b are constants.
Assumption T(1) is known
n is power of b (
General Method
a and b are constants.
If a=2, b=2, T(1)=2 and f(n)=n then solve the above recurrence.
=
= = +3n
In General for any
General Method
a and b are constants.
If
If a=2, b=2, T(1)=2 = and f(n)=n then solve the
above recurrence.
In General for any
If we consider i=
=
General Method
Computing Time is
𝑇 (𝑛)=
{ 𝑔( 𝑛) 𝑛 𝑠𝑚𝑎𝑙𝑙
If we apply
𝑇 (𝑛 1)+ 𝑇 (𝑛 2)+......+𝑇 (𝑛 𝑘 )+ method of
𝑓 (𝑛) 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 }
substitution???
is time to divide and combine.
a and b are constants.
Assumption T(1) is known
n is power of b (
General Method
a and b are constants.
Assumption T(1) is known
n is power of b (
General Method
a and b are constants.
Assumption T(1) is known
n is power of b (
h(n) u(n)
O(1)
General Method
Ex: If a=1, b=2and f(n)=c find T(n)
=c(log n)0
=(log n)
From Table u(n)=
So T(n)=
BINARY SEARCH
Binary Search
Let
Problem: Determining whether the given element ‘x’ is present is
the list or not.
If ‘x’ is present --> find j such that .
Let problem
Let Small(P) is true, if n=1;
S(P) will take value ‘if
Binary Search -- NON-RECURSIVE
Algorithm BinSrch(a, i, l, x)
{
low:=1;high:=n;
while(low)
{
mid:=
if(x<a[mid]) then high:=mid-1;
else if(x>a[mid])then low:=mid+1;
else return mid;
}
retun 0;
}
Algorithm BinSrch(a, i, l, x)
{
if(l=i) then // if Small(p)
{
if(x=a[i]) then return i;
else return 0;
}
else
{
mid :=
if(x=a[mid])then return mid;
else if(x<a[mid])then
return BinSrch(a,i, mid-1,x);
else
return BinSrch(a, mid+1, l,x);
}
}
Lets trace Non-Recursive First
low 1
high 6
mid
x 8
n 7
2 8 9 23 54 82 101
0 1 2 3 4 5 6
Lets trace Non-Recursive First
low 1
high 7
mid (7+1)/2=4
x 8
n 7
2 8 9 23 54 82 101
1 2 3 4 5 6 7
Lets trace Non-Recursive First
low 1
high 4-1 --> 3
mid (7+1)/2=4
8<(a[4]=23) -->TRUE
i
x 8
n 7
2 8 9 23 54 82 101
1 2 3 4 5 6 7
Lets trace Non-Recursive First
low 1
high 4-1 --> 3
mid (1+3)/2=2
x 8
n 7
2 8 9 23 54 82 101
1 2 3 4 5 6 7
Lets trace Non-Recursive First
low 1
high 4-1 --> 3
mid (1+3)/2=2
i 8<(a[2]=8) -->FALSE
l
x 8
n 7
2 8 9 23 54 82 101
1 2 3 4 5 6 7
Lets trace Non-Recursive First
low 1
high 4-1 --> 3
mid (1+3)/2=2
i 8 > (a[2]=8) --> FALSE
l
x 8
n 7
2 8 9 23 54 82 101
1 2 3 4 5 6 7
Lets trace Non-Recursive First
low 1
high 4-1 --> 3
mid (1+3)/2=2
i return 2;
l
x 8
n 7
2 8 9 23 54 82 101
1 2 3 4 5 6 7
Binary Search
Theorem 3.1: Algorithm BinSearch(a,n,x) works correctly
Proof:
1. We assume that all statements work as expected and that
comparisions such as x>a[mid] are approximately carried out.
2. Initially low=1 and hish=n, n≥0 and a[1]≤a[2]≤....≤a[n].
3. If n=0, while loop not entered and returned 0;
4.Possible elements checked for equality are a[low],
a[low+1]......a[mid],.....a[high].
Binary Search
Theorem 3.1: Algorithm BinSearch(a,n,x) works correctly
Proof:
5. If x=a[mid], algorithm terminates successfully.
6. otherwise range is shifted to ‘low’ to ‘mid-1’ or ‘mid+1’ to ‘high’.
7. This change is range will not affect correctness of algorithm as
elements are in sorted order.
8. Even when ‘x’ is not present, low becomes greater than high and
algorithm terminates.
Binary Search
Space Complexity
1. ‘n’ Elements.
2. low, high, mid and x.
Therefore (n+4) locations are required.
Binary Search
Time Complexity
Suppose there are 14 elements in your array,
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]
mid
mid mid
mid mid mid mid
UN-SUCCESS
Binary Search
Time Complexity
Theorem 3.2: If n is in range [2k-1, 2k], then BinSearch
makes at most ‘k’ element comparisions for a successful
search and either k-1 or k comparisions for an
unsuccessful search.
In other words successful search O(log n) and Un
successful is Ө(log n)
Binary Search
Time Complexity
The table can be represented in the form of tree
Binary Search
Time Complexity
I--> Internal Path Length
E--> External Path Length
E->I+2n
= Average number of comparisons in Successful Search
= Average number of comparisons in unsuccessful search
Binary Search
Time Complexity
(n)-1
Best case Ө(1)
Average and Worst case
FINDING MAXIMUM
AND MINIMUM
ELEMENTS
Finding the Maximum and Minimum
Algorithm StrightMaxMin(a, n, max, min)
{
max := min:=a[1];
for i:= 2 to n do
{
if(a[i]>max) then max:=a[i];
if(a[i]<min) then min:=a[i];
}
}
Finding the Maximum and Minimum
Algorithm RecursiveMaxMin(i, j, max, min)
{
if(i:=j) then max:=min:=a[i];
else if(i:=j-1)
{
if(a[i]<a[j])
min:=a[i]; max:=a[j];
else
max:=a[i]; min:=a[j];
}
Finding the Maximum and Minimum
else
max:=a[i]; min:=a[j];
}
else
{
mid:=
RecursiveMaxMin(i , mid, max , min);
RecursiveMaxMin(mid+1 , j , max1 , min1);
if(max1>max) then max:=max1;
if(min1<min) then min:=min1;
}
Finding the Maximum and Minimum
Analysis
Iterative algorithm:
1. n-1 times for loop executed.
2. Comparisions per iteraztion.
3. T(n) is almost 2(n-1) for all the cases.
Finding the Maximum and Minimum
Analysis
Iterative algorithm:
1. What if we replace second if by else if?
2. Now best case is when elements are in ascending order. T(n) is only (n-
1).
3. Worst case --> Descending Order --> 2(n-1)
Finding the Maximum and Minimum
Analysis
Recursive Algorithm.
Divide and Conquer is implemented as follows.
Let P=(n, a[i],......,a[j]), where n is number of elements..
Small(P) is true when n≤2.
If n=1 then max=min=a[i].
If n=2 compare a[i] and a[j] to find max and min;
Else, Divide P into 2 subproblems
Recursively continue it it you enclounter Small(P)
Finding the Maximum and Minimum
Analysis
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
20 10 2 -9 -15 90 30 41 55 36
Finding the Maximum and Minimum
Analysis
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
20 10 2 -9 -15 90 30 41 55 36
1 10 max min
⌊(1+10)/2 ⌋=⌊5 .5 ⌋=5
1 5 max min 6 10 max1 min1
⌊(1+5)/2 ⌋ =3 ⌊(6 +10)/2 ⌋=8
6 8 max min
1 3 max min
⌊(6 +8) /2 ⌋ =7
9 10 max1 min1
⌊(1+3)/2 ⌋ =2 4 5 max1 min1
8 8 max1 min1
3 3 max1 min1
1 2 max min 6 7 max min
Finding the Maximum and Minimum
Analysis
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
20 10 2 -9 -15 90 30 41 55 36
1 10 90 -15
1 5 20 -15 6 10 90 30
6 8 90 30
1 3 20 2
9 10 55 36
4 5 -9 -15
8 8 41 41
3 3 2 2
1 2 20 10 6 7 90 30
Finding the Maximum and Minimum
Analysis
Recursive Algorithm.
If we assome n is some power of 2 for an integer k,
Finding the Maximum and Minimum
Analysis
Iterative -
Recursive-
Time Complexity:
25% of comparisions are saved in recursive.
Space complexity: Recursive needs more space
Space required for n, i, j, max, min, max1 and min1 (7 Elements) in
each call.
We have
MERGE SORT
Merge SOrt
Perfect for Divide and Conquer.
Given array A[0....n-1]
Merge SOrt
ALGORITHM Mergesort()
if n>1
COPY
COPY
Mergesort()
Mergesort()
Merge(B,C,A)
END
Merge SOrt
ALGORITHM Merge()
i←0; j←0;k←0
while i<p and j<q do
{
if then
else
}
if
COPY
else
COPY
Merge SOrt
NOTES
Merge SOrt
• Any algorithm where array is divided into 2 equal parts,
complexity will be .
• Here array is divided and both the halves are sorted. So
complexity will be . (n linear merges).
• O()
QUICK SORT
Quick Sort
Divides array based on VALUE
All the Elements here are > A[s]
𝐴[0]....... 𝐴[𝑆 −1] 𝐴[𝑠 ] 𝐴[𝑠+1]...... 𝐴[𝑛−1]
All the Elements here are < A[s]
Quick Sort
Algorithm Quicksort()
{
if()
Quicksort()
Quicksort()
}
Quick Sort
Algorithm Partition()
{
}
Quick Sort
Best Case Pivot Element always Comes in Middle
Worst Case:
EITHER RIGHT SIDE OR LEFT SIDE WILL BE EMPTY
If array is already in INCREASING ORDER
Quick Sort
WORST CASE
Consider an array in ASCENDING ORDER
After (n+1) Comparisons A[0] Pivot Element will be retained in 0th
Position.
Next remaing elements from 1 to (n-1)..... n comparisons will
happen.
It will continue till as long as last 3 elements are left
Quick Sort
Worst Case
Average Case
ASSUMPTION:
PARTITION SPLIT in position S() with same probability
for n>1,
2n ln n
Quick Sort -- Average Case
Quick Sort -- Average Case
Average Case
When Partition is not even.
Worst such split is one side gets n/4 and other side 3n/4
Maximum level will be
CONSTANT
Quick Sort -- Average Case
Average Case
Strassen’s Matrix Multiplication
Given 2 Square Matrices of size ‘n×n’
Then Divide and Conquer is implemented like this.
We can ob serve 8 multiplications and 4 additions
Strassen’s Matrix Multiplication
Given 2 Square Matrices of size ‘n×n’
Then Divide and Conquer is implemented like this.
We can ob serve 8 multiplications and 4 additions
𝑇 (𝑛)=
{𝑏𝑛≤2
2
8𝑇 (𝑛/2)+𝑐𝑛 𝑛>2
∈𝛰(𝑛
𝑙𝑜𝑔 8
)∈𝑂(𝑛
3
) 2
Strassen’s Matrix Multiplication
Strassens method reduces the recursive calls made.
Strassen’s Matrix Multiplication
Strassens method reduces the recursive calls made.
Strassen’s method reduces the number of
multiplications from 8 to 7.
𝑇 (𝑛)=
{ 𝑏 𝑛 ≤2
2
7 𝑇 (𝑛 /2)+𝑐 𝑛 𝑛 >2
𝑙𝑜𝑔 7
=𝛰 (𝑛 )≈ 𝛰 (𝑛
7 2 .8074
)
Advantages of Divide and Conquer.
Divide and Conquer tend to successfully solve one of the
biggest problems, such as the Tower of Hanoi, a
mathematical puzzle.
It efficiently uses cache memory without occupying much
space.
Advantages of Divide and Conquer.
It is more proficient than that of its counterpart Brute Force
technique.
Since these algorithms inhibit parallelism, it does not involve
any modification and is handled by systems incorporating
parallel processing.
Dis-Advantages of Divide and Conquer.
Since most of its algorithms are designed by incorporating
recursion, so it necessitates high memory management.
An explicit stack may overuse the space.
It may even crash the system if the recursion is performed
rigorously greater than the stack present in the CPU.
Dis-Advantages of Divide and Conquer.
Since most of its algorithms are designed by incorporating
recursion, so it necessitates high memory management.
An explicit stack may overuse the space.
It may even crash the system if the recursion is performed
rigorously greater than the stack present in the CPU.
Decrease and Conquer.
Basic Idea - Exploiting the relationship between a Solution to a
given Instance of a problem and a Solution to its Smaller
Instance.
Decrease and Conquer - Topological Sorting.
Directed Graph: A directed graph, or digraph for short, is a graph
with directions specified for all its edges
Decrease and Conquer - Topological Sorting.
Difference Between Directed and Undirected Graph
1. Adjacency Matrix of directed Graph need not be Symmectric.
2. An edge in a directed graph has just one (not two)
corresponding nodes in the digraph's adjacency lists.
Decrease and Conquer - Topological Sorting.
Depth-first search and breadth-first search are principal traversal
algorithms for traversing digraphs.
Decrease and Conquer - Topological Sorting.
Depth-first search and breadth-first search are principal traversal
algorithms for traversing digraphs.
Back edge in DFS forest of Derected Graph
can connect vertex to its parent
Decrease and Conquer - Topological Sorting.
Depth-first search and breadth-first search are principal traversal
algorithms for traversing digraphs.
The presence of a back edge indicates that
the digraph has a directed cycle.
Other
Decrease and Conquer - Topological Sorting.
A university provides 5 courses, {c1, c2, c3, c4, c5}. They have to
be completed by a student, but there are some conditions to be
met.
1. c1 and c2 dont have any prerequisite.
2. You can take c3 only after completig c1 and c2.
3. You can take c4 only after completing c3.
4. You can take c5 only after completing c3 and c4.
5. Student can take one course per term.
Can you pictorially show the order in which courses should be
taken.!!!!
Decrease and Conquer - Topological Sorting.
The pre-requisites can be represented as a digraph.
the question is whether we can list its vertices in such an order that for every edge
in the graph, the vertex where the edge starts is listed before the vertex where the
edge ends.
Decrease and Conquer - Topological Sorting.
This is the problem statement of Topological Sorting
It is possible if there are no cycles.
That means we need DIRECTED ACYCLIC GRAPH.
Decrease and Conquer - Topological Sorting.
This is the problem statement of Topological Sorting
perform a DFS traversal and note the order in which vertices become dead
ends.
Reversing this order yields a solution to the topological sorting problem
Decrease and Conquer - Topological Sorting.
This is the problem statement of Topological Sorting
perform a DFS traversal and note the order in which vertices become dead
ends.
Reversing this order yields a solution to the topological sorting problem
Decrease and Conquer - Topological Sorting.
Next Algorithm: Source Removal Algorithm.
Repeatedly, identify in a remaining digraph a source - Which is a
vertex with no incoming edges, and delete it along with all edges out
going it.
Problems
Perform Matrix Multiplication using Recursion and Strassens
methodology.
[ ][ ]
12 3 4 567 8
3 21 4 × 1 3 2 4
1212 7856
3 434 3 43 4
Problems
Perform Matrix Multiplication using Recursion and Strassens
methodology.
[ ][ ]
10 0 2 11 1 4 12 3 4
20 0 210 2 4 × 13 2 4
31 0 2 1215 5656
0 3 1 4 17 0 9 5678
Problems
Apply the DFS-based algorithm to solve the topological sorting
problem for the following digraphs.
Problems
Apply quicksort to sort the list
E, X, A, M, P, L, E
in alphabetical order. Draw the tree of the recursive calls made.
