Divide and Conquer Given an array A[1...n]of n elements,where n is a power of 2,it is possible to find both the minimum and maximum of the elements in A using only (3n/2)-2 element comparisons
Divide and Conquer ◼ Given an array A[1…n] of n elements, where n is a power of 2, it is possible to find both the minimum and maximum of the elements in A using only (3n/2)-2 element comparisons
The Divide and Conquer Paradigm The divide step:the input is partitioned into p1 parts,each of size strictly less than n. The conquer step:performing p recursive call(s)if the problem size is greater than some predefined threshold n. The combine step:the solutions to the p recursive call(s)are combined to obtain the desired output
The Divide and Conquer Paradigm ◼ The divide step: the input is partitioned into p1 parts, each of size strictly less than n. ◼ The conquer step: performing p recursive call(s) if the problem size is greater than some predefined threshold n0 . ◼ The combine step: the solutions to the p recursive call(s) are combined to obtain the desired output
The Divide and Conquer Paradigm (1)If the size of the instance /is "small",then solve the problem using a straightforward method and return the answer.Otherwise,continue to the next step; (2)Divide the instance Iinto p subinstances I,B,...,1 of approximately the same size; (3)Recursively call the algorithm on each subinstance 1<p,to obtain p partial solutions; (4)Combine the results of the p partial solutions to obtain the solution to the original instance 2.Return the solution of instance /
The Divide and Conquer Paradigm ◼ (1) If the size of the instance I is “small”, then solve the problem using a straightforward method and return the answer. Otherwise, continue to the next step; ◼ (2) Divide the instance I into p subinstances I1 , I2 , …, Ip of approximately the same size; ◼ (3) Recursively call the algorithm on each subinstance Ij , 1jp, to obtain p partial solutions; ◼ (4) Combine the results of the p partial solutions to obtain the solution to the original instance I. Return the solution of instance I
Selection:Finding the Median and the kth Smallest Element The media of a sequence of n sorted numbers A[1...m]is the“middle”element. If n is odd,then the middle element is the (n+1)/2th element in the sequence. If n is even,then there are two middle elements occurring at positions n/2 and n/2+1.In this case,we will choose the n/2th smallest element. Thus,in both cases,the median is the /2th smallest element. The kth smallest element is a general case
Selection: Finding the Median and the kth Smallest Element ◼ The media of a sequence of n sorted numbers A[1…n] is the “middle” element. ◼ If n is odd, then the middle element is the (n+1)/2th element in the sequence. ◼ If n is even, then there are two middle elements occurring at positions n/2 and n/2+1. In this case, we will choose the n/2th smallest element. ◼ Thus, in both cases, the median is the n/2th smallest element. ◼ The kth smallest element is a general case
Selection:Finding the Median and the kth Smallest Element If we select an element mm among A,then A can be divided in to 3 parts: A={ala∈AIa<mm} 4={ala∈AIa=mm 4,={aa∈AIa>mm}
Selection: Finding the Median and the kth Smallest Element ◼ If we select an element mm among A, then A can be divided in to 3 parts: 1 2 3 A a a A a mm A a a A a mm A a a A a mm = = = = I I I