Post on 04-Jun-2018
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 1/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering
Amrita Vishwa Vid a eetham
Divide and ConquerAlgorithms
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 2/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Introduction Solves computational problem by
Dividing it into subproblems of smaller size
Solve each problem recursively
Merging solutions to sub-problems to produce solution
e.g.,
Merge Sort
Quick Sort
Compleity analyzed using recurrence relations
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 3/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Divide and Conquer
Divide Step!
"f input size smaller than certain threshold solve by
straightfor#ard method
Divide input data into t#o or more dis$oint subsets
%ecur!
%ecursively solve subproblems associated #ith the subsets
Con&uer
'ake the solutions to the subproblems and merge them into
a solution to the original problem
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 4/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Merge Sort (ses divide and con&uer strategy to sort a set of numbers
Divide!
"f S has zero or one element, return S
Divide S into t#o se&uences S) and S
* each containing half
of the elements of S
%ecur
%ecursively apply merge sort to S) and S
*
Con&uer
Merge S) and S
*into a sorted se&uence
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 5/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Merging two sortedsequences
"teratively remove smallest element from one of the t#o
se&uences S) and S
* and add it to end of output se&uence S
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 6/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Merge Sort
12 5 ! 10 15 " 2
10 15 " 2
! 10 15 " 2
12 5 ! 10 15 " 2
12 5 !
12 5
2 5 ! " 10 12 15
5 ! 12 2 " 10 15
5 12 ! 10 15 2 "
12 5 ! 10 15 " 2
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 7/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Merge Sort
mergesort+itemtype s, int lo#, int high/ 0
int i1 23 counter 32
int middle1 23 inde of middle element 32
if +lo# 4 high/ 0
middle 5 +lo#6high/2*1
mergesort+s,lo#,middle/1
mergesort+s,middle6),high/1
merge+s, lo#, middle, high/1
7
7Src: S#iena$ Algorithm Design %an&al$ Chapter '
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 8/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Analysis of Merge Sort
n
n(2 n(2
n(' n(' n(' n('
Height
)*logn+
Time Per Level
)*n+
)*n+
)*n+
)*nlogn+
)*n+
Total Time:
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 9/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Merge Sort: Analysis
#ork done on the kth level involves merging *k pairs
sorted list, each of size n2*k6)
8 total of atmost n-*k comparisons
9inear time for merging at each level
:ach of the n elements appear eactly in one of the
subproblems at each level
%e&uires etra memory
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 10/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Quick Sort
8 divide and con&uer strategy #hich also uses
randomization
Divide
Select a random pivot p. Divide S into t#o subarrays, #here
one contains elements 4 p and the other #hich are ; p
%ecur
Sort subarrays by recursively applying &uicksort on each
subarray
Con&uer
Since the subarrays are already sorted, no #ork is needed in
merge part
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 11/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Quick Sort
12 5 ! 10 15 9 2
12 10
10
5 6 ! 2 12 10 15
2 5 !
2
2 5 ! " 10 12 15
2 5 ! 10 12 15
2 5 ! 10 12
2 10
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 12/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Quick Sort
Q("C<S=%'+8, p, r/
if p 4 r
& 5 >8%'"'"=?+8,p,r/
Q("C<S=%'+8, p, &-)/
Q("C<S=%'+8,& 6), r/
Selection of pivot
Can be first or last element +here/ Median element
%andom element
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 13/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Quick Sort Analysis @orst Case %unning 'ime
=ccurs #hen pivot is al#ays the largest element
Selecting the first element or last element as pivot causes
this problem #hen list is already sorted
%unning time proportional to n6+n-)/6+n-*/6....)
=+n*/
Src: S#iena$ Algorithm Design %an&al$ Chapter ',
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 14/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Average Case Analysis
'he partition in a &uick sort of size s can be
Aood ! if the sizes of partitions are each less than Bs2
8 partition is good #ith the probability
the pivots cause good partitions
Ead ! if one of the partitions has size greater than Bs2
12 5 ! 10 15 " 2
5 6 ! 2 12 10 15
12 5 ! 10 15 " 2
5 ! 10 " 2 15
Aood Ead
2 5 ! " 10 12 15
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 15/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Average Case Analysis
For a node of depth i, #e epect
i2* ancestors are good calls , they are result of good pivots
'he size of the input se&uence for the current call is at
most +B2/i2*n
For a node of depth *logC2Bn,
the epected input size is one
'he epected height of the &uick-sort tree is =+log n/
'he amount or #ork done at the nodes of the same depth
is =+n/
:pected running time of &uicksort is =+nlogn/
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 16/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
In-lace Quick Sort
Quick sort can be implemented #ithout etra memory
%eplace operation used in partition step
:lements less than pivot have rank less than p of pivot
:lements greater than pivot have rank greater than p
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 17/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Quick Sort: artitioning
>8%'"'"=?+8,p, r/ 22inplace partitioning
5 8r
i 5 p-)
for $ 5 p to r-)
if 8$ 45
i 5 i 6 )
echange 8i #ith 8$
echange 8i6) #ith 8r
return i6)
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 18/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
ro!lems
Aiven an array having first n ints and net n chars
85 i) i* iB ... in, c) c* cB ... cn
@rite an in-place algorithm to rearrange the elements of the
array as! 8 5 i) c) i* c* ... in cn
Aive an algorithm to divide an integer array into * sub-
arrays s.t their averages are e&ual i.e average of values of
left array must be same as average of right array
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 19/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
"#ternal Sort: $ucket Sort
8ssumes elements are uniformly distributed
Distribution sort
8rray is partitioned into n e&ual sized subintervals2buckets
:ach interval is a bucket
e.g each bucket can contain element starting #ith a particular
alphabet
:ach bucket sorted separately
Can use bucket sort again (se other sorting techni&ues
:lements from the buckets merged to form the sorted list
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 20/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
$ucket Sort
http:((en,wi#ipedia,org(wi#i(-ile:.&c#et/sort/2,png
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 21/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
$ucket Sort: ro%erties 9et be S be a se&uence of n +key, element/ items #ith keys in
the range G, ? H )
Eucket-sort uses the keys as indices into an auiliary array E of
se&uences +buckets/
<ey-type >roperty 'he keys are used as indices into an array and cannot be arbitrary
ob$ects
?o eternal comparator
Stable Sort >roperty 'he relative order of any t#o items #ith the same key is
preserved after the eecution of the algorithm
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 22/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Methods for $ucketing
"nteger keys in the range a, b
>ut item +k, o/ into bucket Ek H a
String keys from a set D of possible strings, #here D has
constant size +e.g., names of the "ndian states/
Sort D and compute the rank r+k/ of each string k of D in the
sorted se&uence
>ut item +k, o/ into bucket Er+k/
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 23/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
$ucket Sort: seudocode
E(C<:'-S=%'+8/
let EG! ! n ) be a ne# array
n 5 8!length
for i 5 G to n - )
make Ei an empty list
for i 5 ) to n
insert 8i into list Efloor+n 8i/
for i 5 G to n )
sort list Ei #ith insertion sort
concatenate the lists EG,E),....,En together in order
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 24/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
Analysis of $ucket Sort :pected time is =+n/
:ach step takes =+n/ time ecept for sorting each bucket
:pected time to sort bucket Ei is :=+n
i
*/ 5 =+:ni
*
Depends on distribution of each random variable n Aiven n elements and n buckets, probability that a given
element falls in a bucket Ei is )2n
>robability follo#s Einomial distribution
I Mean :ni 5 np 5 ), Jariance Jarni 5 np+)-p/ 5 )-)2n
:ni
* 5 Jarni 6 +:n
i/* 5 ) - )2n 6 )* 5 θ+)/
Substituting in above e&uation epected time is =+n/
@orst case compleity I =+n*
/ +ske#ed distribution/
∑i=)
n
O( E (ni*))
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 25/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
$ucket Sort: "#am%le
Src: Corman$ iest etal$ ntrod&ction to Algorithms4$ !,'
!l
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 26/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
ro!lem
(sing the previous eample as a model, illustrate the
operation of E(C<:'-S=%' on the array 8 +.KL, .)B, .
), ., .BL, .*G, .NL, .OB, .K), .*/.
(se bucket sort to sort the follo#ing elements
+*BB, O, OK, KKK, OO, BB, *K, , KN, LGG, GG, OO,
OB), NKL, N*), *NL, )L*, LO/
Po# are the buckets chosen
& i hi ' d
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 27/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
&e#icogra%hic 'rder
8 d-tuple is a se&uence of d keys +k ), k
*, , k
d/, #here key k
i
is said to be the i-th dimension of the tuple
:ample! coordinates in Bd space
'he leicographic order of t#o d-tuples is recursivelydefined as follo#s
+),
*, ,
d/ 4 +y
), y
*, , y
d/ if
) 4 y) ∨
) 5 y) +∧
*, , d/ 4 +y*, , yd/ i.e., the tuples are compared by the first dimension, then by the
second dimension etc
( di S t
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 28/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
(adi# Sort Specialization of leicographic sort
9eicographic-sort sorts a se&uence of d-tuples in leicographicorder by eecuting a stable sort algorithm d times
%adi sort uses bucket sort for each dimension
8pplicable #here keys in each dimension are integers
:ample!
+K, , / +O, ), O/ +*, , / +*, ), / +B, *, /
+*, ), 4/ +B, *, 4/ +O,), 5/ +K, , 6/ +*, , 6/
+*, 1, / +O,1,O/ +B, *, / +K, 4, / +*, 4, /
+2, ), / +2, , / +3, *, / +5, ), O/ +7, , /
Src: oodrich and 6amassia$ Algorithm Design4
( di S t
8/13/2019 Algo LectureSet3DivConq
http://slidepdf.com/reader/full/algo-lectureset3divconq 29/29
CSE330: Design and Analysis of Algorithms
Vidhya Balasubramanian Amrita School of Engineering Amrita Vishwa Vid a eetham
(adi# Sort %8D"R-S=%'+8,d/
for i 5 ) to d
use a stable sort to sort array 8 on digit "
Aiven n d-digit numbers in #hich each digit can take on up to k
possible values, %8D"R-S=%' correctly sorts these numbers inΘ+d.+n6k// time if the stable sort it uses takes Θ+n6k/ time.
Src: Corman$ iest etal$ ntrod&ction to Algorithms4$ !,3