Introduction to Algorithms
Introduction to Algorithms COT 5407
Popular in Course
Popular in Engineering and Tech
This 15 page Class Notes was uploaded by Connie Schmeler on Monday October 12, 2015. The Class Notes belongs to COT 5407 at Florida International University taught by Giri Narasimhan in Fall. Since its upload, it has received 24 views. For similar materials see /class/221841/cot-5407-florida-international-university in Engineering and Tech at Florida International University.
Reviews for Introduction to Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/12/15
Chapter 9 Medians and Order Statistics The selection problem is the problem of computing given a set A of n distinct numbers and a number 7 1 g 7 g n the ithh order statistics ie the M smallest number of A We will consider some special cases of the order statistics problem a the minimum ie the first 0 the maximum ie the last and o the median ie the halfway point Medians occur at 7 n I 12j and 7 n l 12i If n is odd the median is unique and if n is even there are two medians How many comparisons are necessary and sufficient for computing both the minimum and the maximum Well to compute the maximum n 1 comparisons are necessary and sufficient The same is true for the minimum So the number should be 2n 2 for computing both Actually you can do better by processing the input numbers in pairs Simultaneous computation of max and min can be done in steps Idea Maintain the variables mm and mm Process the n numbers in pairs For the first pair set mm to the smaller and max to the other After that for each new pair compare the smaller with mm and the larger with mam The Algorithm MAX AND MINA n PP PE QWHFWNE I II II I PE LC max lt An mm lt An for 7lt 1 to 712 do if A27L 1 Z A27 then if A27L 1 gt max then max lt A273 1 if A27L lt mm then mm lt A27L else if A27L gt max then max lt A27 if A27L 1 lt min then mm lt A27L 1 return max and mm Selection Selection is a trivial problem if the input numbers are sorted If we use a sorting algorithm having Ong n worst case running time then the selection problem can be solved in in Ong n time But using a sorting is more like using a cannon to shoot a fly since only one number needs to computed 0n expected time selection using the randomized partition Idea In order to find the k th order statistics in a region of size n use the randomized partition to split the region into two subarrays Let s 1 and n s be the size of the left subarray and the size of the right subarray If k s the pivot is the key that s looked for If k g 5 1 look for the k th element in the left subarray Otherwise look for the k s th one in the right subarray Analysis Let Tn be the expected running time Tn For each 7 0 g 7 g n 1 the size of the left subarray is equal to 7 with probability 1n Assuming that the larger interval is taken for some 04 gt O Tn is at most 1 om I Z Tmaxkn k n lngn lk7 s This is at most 2 n l om Z Tk kn2 Analysis cont d Assume that there is c gt 0 such that Tk g ck for all k lt n Then the sum ZZjnm Tk is at most ZZjn ck This is at most n1 n21 1 Z ck Z ck kil krl m 1 5 i3 1 3 lt cnn 1EltE1E 2 2 2 2 Analysis cont d So if c is sufficiently large 3 1 T lt n om c 471 2 By making the constant c at most 404 we have that the 0n is at most Then Tn S on 10 Selection in worst case linear time 1 Divide the elements into groups of five where the last group may have less than five elements in case when the input array size is not a multiple of five Compute the median of each group ties can be broken arbitrarily Make a recursive call to calculate the median of the medians Set 1 to the median 4 Use 1 as the pivot and partition 5 If the pivot is not the order statistics that is searched for recurse on the subarray that contains it Use a bound B to stop recursion If the size of the array is less than or equal to B then use brute force search to find the desired order statics 11 t S 1 X e t 0 n y a m 12 Analysis Assume that the input numbers are pairwise distinct We claim that there is a constant 04 such that for all n 2 1 Tn the running time of this method is at most om As long as B is set to a constant we can adjust a value of 04 so that the claim holds for all n S B 13 Analysis cont d Let n gt B The number of medians is g 50 it is at most gg 1 and is at least The number of medians less than 1 is at least 1 0 2 So the size of the smaller subarray is at least 31n O 2 2 8 6 Thus the size of the larger subarray is at most 8 6 Let B be a constant such that the running time for the other things requires at most n Then the total running time is n 7n 1 6 nalt5 1O Thisis 9 n l l gn l 7a 6 10 7 an n 10m a which isgomif 1 n gn I 7QSO 14 1 n gn I 7QSO 1OBn n 7O04 Z 0 TL n 70 Let B 140 choose 04 2 203 to Show Tn S am 02103
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'