### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Introduction to Algorithms COT 5407

FIU

GPA 3.57

### View Full Document

## 24

## 0

## 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

### 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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.