Advanced Data Structures: Selection Algorithms Overview
Explore various selection algorithms including Randomized Selection Algorithm and Deterministic Selection Algorithm, their applications, theoretical foundations, and comparison models. Learn how these algorithms are used to find the kth smallest element in an array efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Advanced Data Structures (Random topics Gerth finds interesting...) Gerth St lting Brodal 1
Formalities Versions of course: normal , 3 implementation projects, groups 2-3 people honours , 4 theoretical projects, individual Exam: Individual discussion about projects (Jan.) Literature: Research papers Lectures: High level discription of ideas 2
Problem Input: Unordered list (x1,x2,...xn) and y1<y2< <yk Output: For each yidetermine if yiis in the list *Comparison model 3
Selection [T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 2001, Chapter 9.3] Original [M. Blum, R.W. Floyd, V. Pratt, R. Rivest and R. Tarjan, Time bounds for selection, J. Comp. Syst. Sci. 7 (1973) 448-461] Problem: Given an array A of n elements and an integer k, find the k th smallest element in A A 3 7 8 2 9 15 28 6 5 13 3 rd smallest (k=3) 4
Randomized Selection Algorithm [C. A. R. Hoare: Algorithm 65: find. Commun. ACM 4(7): 321-322 (1961)] Algorithm QuickSelect(A,k) p = random element from A A<= { e | e A and e < p } A>= { e | e A and e > p } if |A<|= k-1 then return p if |A<|> k-1 then return QuickSelect(A<,k) return QuickSelect(A>, k-|A<|-1) Thm QuickSelect runs in expected O(n) time i= ( 3 ( n / 4 ) ) ( ) O O n Proof = 0 i 5
Deterministic Selection Algorithm [M. Blum, R.W. Floyd, V. Pratt, R. Rivest and R. Tarjan, Time bounds for selection, J. Comp. Syst. Sci. 7 (1973) 448-461] Algorithm Select(A,k) if |A|= 1 then A[1] A n/5 groups ... 2 4 1 3 7 8 6 4 2 10 9 11 3 2 12 5 5 5 A p = Select(A ,|A |/2) A<= { e | e A and e < p } A>= { e | e A and e > p } if |A<|= k-1 then return p if |A<|> k-1 then return Select(A<,k) return Select(A>, k-|A<|-1) n/5 medians, one for each group 3 6 9 ... 6
Deterministic Selection Algorithm Thm Select runs in worst-case O(n) time Proof = 1 1 n = ( ) T n + + ( ) 5 / ( 7 / 10 ) otherwise n T n T n = O(n) 1 2 3 n/10+1 n/5 <p 1 2 2 ... 2 4 3 ... A 3 6 9 ... p >p 4 8 11 ... 7 10 12 ... consider each group as a sorted column 7
Application: Lazy Construction of Search Trees [Y.-T. Ching, K. Mehlhorn, M.H.M. Smid: Dynamic Deferred Data Structuring. Inf. Process. Lett. (IPL) 35(1):37-40 (1990)] 1 10 3 6 2 15 12 7 14 13 8 4 5 11 9 8 4 12 2 6 10 14 1 3 5 7 9 11 13 15 Construction T= sorting = O(n log n) Searching O(log n) Construction + k searches O((n+k) log n) 8
Application: Lazy Construction of Search Trees 1 10 3 6 2 15 12 7 14 13 8 4 5 11 9 Find root using selection/median and recurse 8 4 12 2 6 10 14 1 3 5 7 9 11 13 15 Construction O(n log n) 9
Application: Lazy Construction of Search Trees 1 10 3 6 2 15 12 7 14 13 8 4 5 11 9 8 % 4 12 2 6 10 14 % 1 3 5 7 9 11 13 15 Search(7) Lazy construct nodes on 1 search path: 1+2+4+ +n/2+n=O(n) 10
Application: Lazy Construction of Search Trees Thm Lazy construction + k searches worst-case O(n log k) time Proof log k levels completely build O(n) time per level k leaf paths O(n/k) time per leaf 11
Thm Lazy construction + k searches requires worst-case (n log k) time Proof Consider the elements of the input array in sorted order, and consider k unsuccessful search keys y1< <yk. The algorithm must determine the color (inteval between two search keys) of each element in the input array, otherwise an element could have been equal to a search key. There are (k+1)ncolorings. A dicision tree must determine the coloring. Decision tree depth is log2(k+1)n= n log2(k+1) y1 y2 yk unsuccesfull searches 12
