ALGORITHM ANALYSIS AND DESIGN

DIVIDE AND CONQUER

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

1

May 6, 2015 2:15 AM Algorithm Analysis and Design

Problem

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

solution

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

2

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.

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

3

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

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

4

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));}}

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

5

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

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

6

May 6, 2015 2:15 AM Algorithm Analysis and Design

Time Complexity Contd..

• In general
• T(n)=n ^logb^a [t(1)+u(n)] where u(n)= _j=1ε^k h(bj)
• H(n)=f(n)/ n ^logb^a

• If h(n) is O(n^r ) for r>0 then u(n) is O(1)
• If h(n) is θ(logn^r ) for r=>0 then u(n) is θ(logn^r+1 / (r+1))
• If h(n) is Ω (n^r ) for r>0 then u(n) is θ(h(n))

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

7

May 6, 2015 2:15 AM Algorithm Analysis and Design

Example

_{T(n) =} 1 for n=1

T(n/2)+c for n>1

h(n)=f(n)/n^{log b a}=c*(logn)⁰

So u(n)= θ(logn)

T(n)=n ^{log 1} [c+ θ (logn)] = θ (logn)

​

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

8

May 6, 2015 2:15 AM Algorithm Analysis and Design

Binary Search

Algorithm binsearch(a,i,j,x)

{if (i=j) then

{ if (x=a[i]) then return i;

else return 0; }

else

{mid:= (i+j) div 2;

if (x=a[mid] then return mid;

else if (x<a[mid]) then

return binsearch(a,i,mid-1,x);

else return binsearch(a,mid+1,j,x); }}

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

9

May 6, 2015 2:15 AM Algorithm Analysis and Design

Computing Complexity

1 3 5 7 9 11 13

Unsuccessfull cases

Example

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

10

May 6, 2015 2:15 AM Algorithm Analysis and Design

Binary Search Complexity �

• unsuccessful search θ (logn)
• Successful
• best - θ (1)
• worst – when leaf node is reached - θ(logn)

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

11

May 6, 2015 2:15 AM Algorithm Analysis and Design

Average Case Complexity

T(n)= 2⁰*1+2 ¹*2+- - - + 2 ^k-1 * k

= [2¹*1+2 ²*2+- - - + 2 ^k-1 *( k-1)] +[ 2⁰+2 ¹+- - - + 2 ^k-1 ]

= [( k-2)* 2 ^k-1+2] + [2^(k+1)-1]

since we have _i=1 ε ^k i*2ⁱ =(k-1)*2^(k+1)+2

=k*2 ^k+2

=θ (nlogn)

so average case complexity θ(logn)

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

12

May 6, 2015 2:15 AM Algorithm Analysis and Design

Finding Max & Min

Algorithm smaxmin(i,j,n,max,min)

{max:=a[1]; min:=a[1];

For i:= 2to n do

{if (a[i]>max) then max:=a[i];

if (a[i]<min) then min:=a[i];

}}

2(n-1) Comparisons

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

13

May 6, 2015 2:15 AM Algorithm Analysis and Design

Improvement

Algorithm smaxmin(i,j,n,max,min)

{max:=a[1]; min:=a[1];

For i:= 2to n do

{if (a[i]>max) then max:=a[i];

else if (a[i]<min) then min:=a[i];

}}

Worst case- sorted in descending order - 2(n-1) Comparisons

Best case- sorted in ascending order - n-1Comparisons

Average case – half cases a[i] is greater - n/2+(n-1) =3n/2 -1

​

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

14

May 6, 2015 2:15 AM Algorithm Analysis and Design

Divide and Conquer Approach

• Split input into smaller subsets
• Repeat until input size is 1 or 2

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

15

May 6, 2015 2:15 AM Algorithm Analysis and Design

MAXMIN

Algorithm maxmin(i,j,max,min)

{if (i=j) then max:=min:=a[i];

else if (i=j-1) then

if (a[i]<a[j]) then

{max:=a[j];min:=a[i];}

else {max:=a[i];min:=a[j];}}

else

{ mid:= L(i+j)/2 ;

maxmin( i,mid,max,min);

maxmin(mid+1,j,max1,min1);

if (max<max1) then max:=max1;

if (min>min1) then min:= min1;}}

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

16

May 6, 2015 2:15 AM Algorithm Analysis and Design

Time Complexity

T(n)= T(n/2)+T(n/2)+2 for n>2; =1 for n=2

When n is a power of 2, T(n) = 2*T(n/2) +2

= - - - - -

= 2 ^k-1 *T(2) +2* (2 ^k-1 –1) = 2 ^k-1 +2 ^k –2

= 3*n/2 –2

it is the best, average and worst case complexity.

Compared to the 2n-1 comparisons of straight maxmin this approach is better.

But it requires logn +1 levels of stack.

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

17

May 6, 2015 2:15 AM Algorithm Analysis and Design

Considering Index Comparisons

• When element and index comparisons of the same cost
• In languages that does not support switch statement modification required

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

18

May 6, 2015 2:15 AM Algorithm Analysis and Design

Improvement

Algorithm maxmin(i,j,max,min)

{if (i > j) then

if (a[i]<a[j]) then {max:=a[j];min:=a[i];}

else {max:=a[i];min:=a[j];}}

else

{ mid:= L(i+j)/2 ;

maxmin( i,mid,max,min);

maxmin(mid+1,j,max1,min1);

if max<max1) then max:=max1;

if (min>min1) then min:= min1;}}

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

19

May 6, 2015 2:15 AM Algorithm Analysis and Design

Complexity

C(n)= 2* C(n/2)+3 for n>2

=2 for n=2

• unfolding recurrence
• C(n) = 2 ^k-1*C(2) + 3* ₀ε ^k-2 2ⁱ

=2 ^k +3* 2 ^k-1 –3

=5n/2 –3

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

20

May 6, 2015 2:15 AM Algorithm Analysis and Design

Comparison

​

• Better than straight maxmin 3*(n-1)
• Practically slower due the overhead of stacking

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

21

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).�

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

22

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

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

23

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);

}}

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

24

May 6, 2015 2:15 AM Algorithm Analysis and Design

Algorithm Merge

Algorithm merge(low,mid,high)

{h:=low;i:=low; j:=mid+1;

while ((h<=mid) and (j<=high)) do

{if (a[h]<=a[j]) then

{b[i]:=a[h];h:=h+1;}

else

{b[i]:=a[j];j:=j+1;}

i:=i+1;}

if (h>mid) then

for k:=j to high do

{b[i]:=a[k];i:=i+1;}

else

for k:=h to mid do

{b[i]:=a[k];i := i+1;}

for k:=low to high do a[k]:=b[k];

}

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

25

May 6, 2015 2:15 AM Algorithm Analysis and Design

Complexity

• Unfolding recurrence

T(n) = 2 T(n/2) + cn

= 2² T(n/4) + 2cn

= 2^k T(n/2^k) + kcn

= 2^k T(1) +kcn = an + cn log n

= O(n log n)

T(n)= 2*T(n/2)+cn for n>1

a for n=1

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

26

May 6, 2015 2:15 AM Algorithm Analysis and Design

Refinements

• 2n locations – Extra n locations
• Associate an extra field with key
• For small values of n recursion inefficient
• Much time is wasted on stacking.
• Use an efficient nonrecursive sort for small n

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

27

May 6, 2015 2:15 AM Algorithm Analysis and Design

Refinement 1

Algorithm insertion sort(a,n)

{for j:=2 to n do

{ item := a[j]; i := j-1;

while ((i>=1) and (item<a[j])) do

{a[i+1]:= a[i]; i := i-1; }

a[i+1] := item; } }

For n<16 insertion sort is used.

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

28

May 6, 2015 2:15 AM Algorithm Analysis and Design

Complexity

• Insertion sort for worst case
• ₂ ε ⁿ j=n(n+1)/2-1=θ(N²).
• In the best case
• θ(N).

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

29

May 6, 2015 2:15 AM Algorithm Analysis and Design

Algorithm2

algorithm mergesort2(low,high)

{if (high-low)<15 then ///when size is <16

return insertionsort1(a,link,low,high)

else

{ mid := L(low+high)/2  ///divides into 2

q:=mergesort(low,mid);

r:=mergesort(mid+1,high);

return merge1(q,r);}}

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

30

May 6, 2015 2:15 AM Algorithm Analysis and Design

Refinement 2

• An auxillary array with values 0..n used
• Each index points to the original array

​

• Interpreted as pointers to elements of a

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

31

May 6, 2015 2:15 AM Algorithm Analysis and Design

Demonstration

• Interpreted as pointers to elements of a

1

3

6

8

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

32

May 6, 2015 2:15 AM Algorithm Analysis and Design

Demonstration Contd..

3

1

6

8

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

33

May 6, 2015 2:15 AM Algorithm Analysis and Design

Demonstration Contd..

5

4

3

1

7

Sorting Over

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

34

May 6, 2015 2:15 AM Algorithm Analysis and Design

Algorithm3

Algorithm merge1(q,r)

{i:=q;j:=r;k:=0;

while ((i<>0) and j<>0)) do

{if (a[i] < a[j]) then

{link[k]:=i;k:=i;i:=link[i];}

else {link[k]:=j;k:=j;j:=link[j];}}

If (i = 0) then link[k]:=j; else link[k]:=i;

return link[0];}

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

35

May 6, 2015 2:15 AM Algorithm Analysis and Design

Quick Sort

• To avoid the complexity for merging
• division to subarrays made specially
• 2 main algorithms
• Quick Sort
• Partition

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

36

May 6, 2015 2:15 AM Algorithm Analysis and Design

Working Principle

• Decides the partition element
• Divides into 2 subarrays based on partition element
• Performs Recursive invocation to sort the subarrays.

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

37

May 6, 2015 2:15 AM Algorithm Analysis and Design

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.

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

38

May 6, 2015 2:15 AM Algorithm Analysis and Design

Working

• if the size of the array is n, partition requires n+1 comparisons.

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

39

May 6, 2015 2:15 AM Algorithm Analysis and Design

Algorithm Quicksort

Algorithm quicksort(p,q)

{ if (p<q) then

{j:=partition(a,p,q+1);

quicksort(p,j-1);

quicksort(j+1,q);}}

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

40

May 6, 2015 2:15 AM Algorithm Analysis and Design

Algorithm Partition

algorithm partition(a,m,p)

{v:=a[m]; i:=m; j:=p;

repeat

{ repeat

i:= i+1;

until (a[i]>=v);

repeat

j:= j-1;

until (a[j]<=v);

if (i<j) then

{temp:=a[i];

a[i]:=a[j];

a[j]:=temp;}

until (i>=j);

a[m]:=a[j];

a[j]:=v;

return j;}

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

41

May 6, 2015 2:15 AM Algorithm Analysis and Design

Complexity

• if the size of the array is n, partition requires n+1 comparisons.

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

42

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

= 2² T(n/4) + an + an

= 2^k T(n/2^k) + akn

= n + an log n

= O(n log n)

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

43

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(n²)

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

44

May 6, 2015 2:15 AM Algorithm Analysis and Design

Average Case�

Ca(N)= n+1 + ₁ ε ^k (Ca(k-1)+Ca(n-k))

Ca(N)= n+1 +1/n* ₁ ε ^k (Ca(k-1)+Ca(n-k))

n*Ca(n)= n*(n+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

= ₃ ε ⁿ⁺¹ (1/k) + Ca(1)/2

<= 1/x dx = log(n+1)-log 2 = O(logn) So Complexity is O(nlogn)

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

45

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

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

46

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(n³) if both matrices are n x n

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

47

May 6, 2015 2:15 AM Algorithm Analysis and Design

Divide and Conquer Approach

 A₁₁ A₁₂ B₁₁ B₁₂ C₁₁ C_12]

A₂₁ A₂₂ B₂₁ B₂₂ C₂₁ C_22]

C₁₁=A₁₁B₁₁+ A₁₂B₂₁

C₁₂=A₁₁B₁₂+ A₁₂B₂₂

C₂₁=A₂₁B₁₁+ A₂₂B₂₁

C₂₂=A₂₁B₁₂+ A₂₂B₂₂

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

48

May 6, 2015 2:15 AM Algorithm Analysis and Design

Complexity

T(n)= a for n<=2

= 8 T(n/2)+cn² for n>2

T(n)= 8 T(n/2)+cn²

= 8[8 T(n/2²)+c(n/2)² ]+cn²

= 8² T(n/2²)+2cn² +cn²

= 8³ T(n/2³)+2²cn² + 2cn² + cn²

- - - - - - - - - - - - -

= 8^k T(n/2^k)+2^k-1cn² + - -+2cn² + cn²

= 8^k* a +[2^k-1]cn² = a*(2³ )^k +[n-1]cn²=O(n³)

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

49

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.

​

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

50

May 6, 2015 2:15 AM 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.

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

51

May 6, 2015 2:15 AM Algorithm Analysis and Design

Formulation

P=( A₁₁ +A₂₂ ) (B₁₁+ B₂₂)

Q=( A₂₁ +A₂₂ ) B₁₁

R= A₁₁ (B₁₂ - B₂₂)

S = A₂₂ (B₂₁ – B₁₁)

T=( A₁₁ +A₁₂ ) B₂₂

U=( A₂₁ – A₁₁ ) (B₁₁+ B₁₂)

V=( A₁₂ - A₂₂ ) (B₂₁+ B₂₂) 

C₁₁=P+S-T+V

C₁₂= R+ T

C₂₁=Q+S

C₂₂= P+R-Q+U

• 7 multiplications and 6 additions and 4 subtractions.
• 6 additions and 2 subtractions

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

52

May 6, 2015 2:15 AM Algorithm Analysis and Design

Complexity

T(n)= a for n<=2

= 7 T(n/2)+cn² for n>2

T(n)= 7 T(n/2)+cn² = 7[7 T(n/2²)+c(n/2)² ]+cn²

= 7² T(n/2²)+(7/4)cn² +cn²

- - - - - - - - - - - - -

= 7^k T(n/2^k)+ (7/4) ^k-1cn² + - -+ (7/4) cn² + cn²

= 7^k* a +[(7/4) ^k-1]cn² / [7/4-1]

≡ a* 7^logn +(7/4) ^logn*cn²= a* n^log7 +n ^logn7/4*cn²

= a* n^log7 +c*n ^{logn7-log 4+log 4} = O(n^{log 7}) = O(n^2.81)

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

53

May 6, 2015 2:15 AM Algorithm Analysis and Design

Discussion

• Straight and stressen’s cross over point – n>100
• No remarkable speed up is achieved for any serious application by implementing Strassen's algorithm.
• The fastest known algorithm, devised in 1987 by Don Coppersmith and Shmuel Winograd, runs in O(n^2.38) time.
• Use the principle of arithmetic progressions to perform matrix multiplications.

​

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

54

May 6, 2015 2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

55