ALGORITHM ANALYSIS AND
DESIGN
DIVIDE AND CONQUER
Algorithm Analysis and Design
Strategy
• Given a function on n inputs
– input splitted into k disjoint subsets
– yielding k subproblems.
• Solve subproblems
• Combine the subsolutions into a
solution
solution
Problem Problem
May 6, 2015 2:15 AM Algorithm Analysis and Design
Solving Subproblems
• Large Subproblems
– Solved by reapplication of divide and conquer.
– Subproblems same type as the original problem
implemented using recursive algorithm
• Smaller subproblems solved independently.
May 6, 2015 2:15 AM Algorithm Analysis and Design
Control Abstraction
• Procedure whose flow of control is clear.
• Primary operations are specified by other
procedures whose precise meanings are left
undefined
May 6, 2015 2:15 AM Algorithm Analysis and Design
Control Abstraction for DandC
Algorithm DandC(P)
{ if small(P) then return(P);
else
{divide P into smaller instances P1,P2,- - -, Pk for k>1
apply DandC to each subproblem ;
return combine(DandC(P1),- - - ,DandC(Pk));}}
May 6, 2015 08:04 PM Algorithm Analysis and Design
Time Complexity
T(n) = g(n) when n is small
T(n1)+T(n2)+- - -+T(nk)+f(n)
• when subproblems are similar, complexity
can be represented by a recurrence
T(n) = T(1) n=1
a* T(n/b) +f(n) n>1
May 6, 2015 2:15 AM Algorithm Analysis and Design
Summary
• When element comparisons are costlier dandc yields
a better algorithm.
• Dandc always willnot give better algorithm.
– Only a design technique that will guide to better designs.
• Constants should be specified, during comparisons if
relevant( when both has same order complexity).
May 6, 2015 2:15 AM Algorithm Analysis and Design
Merge Sort
• Divides list into two sub lists
• Sort sub lists separately
– Recursive invocation
• Merges the sub lists
25 11 18 17 13 45 28 30
May 6, 2015 2:15 AM Algorithm Analysis and Design
Algorithm Mergesort
Algorithm mergesort(low,high)
{ if (low<high) then
{ mid:= L (low+high)/2
megesort(low,mid);
mergesort(mid+1,high);
mege(low,mid,high);
}}
May 6, 2015 2:15 AM Algorithm Analysis and Design
Algorithm Merge
Algorithm merge(low,mid,high) if (h>mid) then
{h:=low;i:=low; j:=mid+1; for k=j to high do
while ((h<=mid) and (j<=high)) {b[i]=a[k];i=i+1;}
do else
{if (a[h]<=a[j]) then for k=h to mid do
{b[i]=a[h];h=h+1;} {b[i]=a[k];i = i+1;}
else for k=low to high do
{b[i]=a[j];j=j+1;} a[k]=b[k];
i=i+1;} }
May 6, 2015 2:15 AM Algorithm Analysis and Design
Complexity
T(n)= 2*T(n/2)+cn for n>1
a for n=1
• Unfolding recurrence
T(n) = 2 T(n/2) + cn
= 22 T(n/4) + 2cn
= 2k T(n/2k) + kcn
= 2k T(1) +kcn = an + cn log n
= O(n log n)
May 6, 2015 2:15 AM Algorithm Analysis and Design
Complexity
• Insertion sort for worst case
– 2 ε n j=n(n+1)/2-1=θ(N2).
• In the best case
– θ(N).
Quick Sort
• To avoid the complexity for merging
– division to subarrays made specially
• 2 main algorithms
– Quick Sort
– Partition
Working Principle
• Decides the partition element
• Divides into 2 subarrays based on partition
element
• Performs Recursive invocation to sort the
subarrays.
Partition
• Arranges the elements around the pivot
element
• All the elements less than pivot are moved to
left side (smaller indices) of the pivot
• All elements greater than the pivot are moved
to the right side of the pivot.
Working
• if the size of the array is n, partition requires
n+1 comparisons.
25 11 18 17 13 45 28 30
13 11 18 17 25 45 28 30
Algorithm Quicksort
Algorithm quicksort(p,q)
{ if (p<q) then
{j:=partition(a,p,q+1);
quicksort(p,j-1);
quicksort(j+1,q);}}
Algorithm Partition
algorithm partition(a,m,p) if (i<j) then
{v:=a[m]; i:=m; j:=p; {temp:=a[i];
repeat a[i]:=a[j];
{ repeat
a[j]:=temp;}
i:= i+1;
until (i>=j);
until (a[i]>=v);
a[m]:=a[j];
repeat
j:= j-1; a[j]:=v;
until (a[j]<=v); return j;}
May 6, 2015 2:15 AM Algorithm Analysis and Design
Complexity
• if the size of the array is n, partition requires
n+1 comparisons.
25 11 18 17 13 45 28 30
May 6, 2015 2:15 AM Algorithm Analysis and Design
Best Case Complexity
• best case is when pivot is the middle element
and the 2 subarrays are of equal size.
T(n) = 2 T(n/2) + an
= 22 T(n/4) + an + an
= 2k T(n/2k) + akn
= n + an log n
= O(n log n)
May 6, 2015 2:15 AM Algorithm Analysis and Design
Worst Case Complexity
• worst case is when pivot is either the smallest or the
largest and the subarrays will be of size 0 and n-1.
• it will have maximum level of recursion and during
each recursion the size of the subarray gets reduced
by just one.
• Different subarrays of size r = n, n-1, - - ,2
• Total comparisons required =
= O(n2)
May 6, 2015 2:15 AM Algorithm Analysis and Design
Average Case
Ca(N)= n+1 + 1 ε k (Ca(k-1)+Ca(n-k))
Ca(N)= n+1 +1/n* 1 ε k (Ca(k-1)+Ca(n-k))
n*Ca(n)= n*(n+1) + 1 ε k (Ca(k-1)+Ca(n-k))
= n*(n+1) +2[ca(0)+Ca(1)+- - - + Ca(n-1)]
(n-1)*Ca(n-1) = n*(n-1) +2[ca(0)+Ca(1)+- - - + Ca(n-2)]
(n)*Ca(n)- (n-1)*Ca(n-1) = 2*n +2*Ca(n-1)
Ca (n) 2 + Ca(n-1)
=
n+1 n+1 n
Ca (n) 2 + 2 + Ca(n-2)
=
n+1 n+1 n n-1
= 3 ε n+1 (1/k) + Ca(1)/2
May 6, 2015 2:15 AM Algorithm Analysis and Design
Comparison
• Maximum recursion n-1
• Improvements :
– Selection of pivot element
• Sub arrays are approximately of equal size
– Reduce level of recursion
• Sort small sub array first
May 6, 2015 2:15 AM Algorithm Analysis and Design
Matrix Multiplication
For i:= 1 to m
For j:=1 to p
c[i,j]:=0;
For k:= 1 to n
c[i,j]:=c[i,j] + a[i,k]*b[k,j]
Complexity is O(mnp)
Complexity is O(n3) if both matrices are n x n
May 6, 2015 2:15 AM Algorithm Analysis and Design
Divide and Conquer Approach
[ [ [
A11
A21
A12
[
A22 X
B11
B21
[
B12
B22 =
C11
C21
C12]
C22]
[
C11=A11B11+ A12B21 a11 a12 a13 a14 b11 b12 b13 b14 c11 c12 c13 c14
a21 a22 a23 a24 b21 b22 b23 b24 c21 c22 c23 c24
C12=A11B12+ A12B22
a31 a32 a33 a34 b31 b32 b33 b34 c31 c32 c33 c34
C21=A21B11+ A22B21 a41 a42 a43 a44 b41 b42 b43 b44 c41 c42 c43 c44
C22=A21B12+ A22B22
May 6, 2015 2:15 AM Algorithm Analysis and Design
T(n)= a for n<=2
Complexity = 8 T(n/2)+cn2 for n>2
T(n)= 8 T(n/2)+cn2
= 8[8 T(n/22)+c(n/2)2 ]+cn2
= 82 T(n/22)+2cn2 +cn2
= 83 T(n/23)+22cn2 + 2cn2 + cn2
------------ -
= 8k T(n/2k)+2k-1cn2 + - -+2cn2 + cn2
= 8k* a +[2k-1]cn2 = a*(23 )k +[n-1]cn2=O(n3)
May 6, 2015 2:15 AM Algorithm Analysis and Design
Refinements
• Reformulate the equations for Cij so as to
have fewer matrix multiplications.
• Faster algorithms exist
– Clever divide-and-conquer recurrences.
• Mr Volker Strassen
– Fewer than 8 matrix maultiplications.
Algorithm Analysis and Design
Strassen’s Multiplication
• 7 submatrix multiplications
• 18 additions /subtractions of matrices.
• Principle
– 7 temporary sub matrices P,Q,R,S,T,U,V computed.
May 6, 2015 2:15 AM Algorithm Analysis and Design
Formulation
P=( A11 +A22 ) (B11+ B22)
Q=( A21 +A22 ) B11 C11=P+S-T+V
R= A11 (B12 - B22) C12= R+ T
S = A22 (B21 – B11)
C21=Q+S
T=( A11 +A12 ) B22
U=( A21 – A11 ) (B11+ B12) C22= P+R-Q+U
V=( A12 - A22 ) (B21+ B22)
• 7 multiplications and 6 additions and 4
subtractions.
May 6, 2015 2:15 AM Algorithm Analysis and Design
T(n)= a for n<=2
Complexity = 7 T(n/2)+cn2 for n>2
T(n)= 7 T(n/2)+cn2 = 7[7 T(n/22)+c(n/2)2 ]+cn2
= 72 T(n/22)+(7/4)cn2 +cn2
------------ -
= 7k T(n/2k)+ (7/4) k-1cn2 + - -+ (7/4) cn2 + cn2
= 7k* a +[(7/4) k-1]cn2 / [7/4-1]
≡ a* 7logn +(7/4) logn*cn2= a* nlog7 +n logn7/4*cn2
= a* nlog7 +c*n logn7-log 4+log 4 = O(nlog 7) = O(n2.81)
Decrease-and-Conquer
The decrease-and-conquer technique is based on exploiting the
relationship between a solution to a given instance of a problem and a
solution to a smaller instance of the same problem.
Three major variations of decrease-and-conquer:
i). decrease by a constant
ii). decrease by a constant factor
iii). variable size decrease
Example: an= an-1. a
Decrease by Variable Factor:
Example: gcd(m, n) = gcd(n, m mod n).
Insertion Sort
Topological Sorting
A directed graph, or digraph for short, is a graph with directions specified for all
its edges
Topological sorting: 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.
Master Theorem
Binary Tree Traversals and Related Properties
A binary tree T is defined as a finite set of nodes that is either empty or consists
of a root and two disjoint binary trees TL and TR called, respectively, the left
and right subtree of the root.
For the empty tree, the comparison T = 0 is executed once but
there are no additions, and for a single-node tree, the comparison
and addition numbers are three and one, respectively.
• The number of external nodes x is always one more than the number of internal nodes n: x=n+1
• Total Nodes in a Binary Tree : 2n + 1= x + n
• The number of comparisons to check whether the tree is empty is: C(n) = n+x = 2n+1
• while the number of additions is : A(n) = n.
Multiplication of large Integers
The classic pen-and-pencil algorithm for multiplying two n-digit integers,
each of the n digits of the first number is multiplied by each of the n digits
of the second number for the total of n2 digit multiplications.
Example : 23 X 14
To multiply two n-digit integers a and b where n is a positive even number
using Divide and Conquer, divide a and b into two halves,
i.e., a=a1a0 =
and b=b1b0 =
Time Complexity
No. of Multiplications= 3
