Algorithms Design And Analysis
Algorithms Design And Analysis CS 422
Popular in Course
Popular in ComputerScienence
This 1 page Class Notes was uploaded by Kavon Reynolds on Thursday October 15, 2015. The Class Notes belongs to CS 422 at Northern Michigan University taught by Michael Kowalczyk in Fall. Since its upload, it has received 34 views. For similar materials see /class/224055/cs-422-northern-michigan-university in ComputerScienence at Northern Michigan University.
Reviews for Algorithms Design And Analysis
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/15/15
Algorithm Design and Analysis 2252008 Lecture 19 Linear time selection Instructor Mike Kowalczyk 1 Linear time selection 11 De ne the problem First let s de ne the problem carefully Selection problem lnput Array of n elements and index 0 g k g n 7 1 Output Returns AM where A is the sorted version of A Note that our problem de nition doesn t necessarily say that we actually sort the array it s just a way of specifying the output 12 Divide and conquer algorithm Our idea starts with grouping the n elements in sets of 5 each Then sort each group of 5 take the median of each of group of 5 and recursively nd the median of those medians of 5 Now we know that the median of medians is going to be greater than approximately 37110 elements Similarly it s less than 37110 elements so the median of medians is somewhere from the 310 mark to the 710 mark Because of this we can use the median of medians as a pivot and split up the remaining work just like Quicksort The fact that the pivot is roughly in the middle means that it should be fast but we ll prove this to make sure selectionarray A index k Group A into sets of 5 elements each Sort each set of 5 Let M be the set of medians of those sets of 5 if M is size 1 return MO p selectionM Mlength 2 finds the median of M Use the pivot p to split A into arrays S and B Let S the elements of A that are smaller than p Let B the elements of A that are bigger than p if ISI k ISI denotes the number of elements in S return p else if k lt Isl return selectionS k else k gt ISI