tailieunhanh - Lecture Data structures and algorithms in Java (6th edition): Chapter 13.5 - Goodrich, Tamassia, Goldwasser

This chapter provides knowledge of selection. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Selection 3/29/14 21:22 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Selection © 2014 Goodrich, Tamassia, Goldwasser Selection 1 The Selection Problem ! Given an integer k and n elements x1, x2, , xn, taken from a total order, find the k-th smallest element in this set. ! Of course, we can sort the set in O(n log n) time and then index the k-th element. k=3 7 4 9 6 2 → 2 4 6 7 9 ! Can we solve the selection problem faster? © 2014 Goodrich, Tamassia, Goldwasser Selection 2 1 Selection 3/29/14 21:22 Quick-Select ! Quick-select is a randomized selection algorithm based on the prune-and-search paradigm: n   x Prune: pick a random element x (called pivot) and partition S into x w   L: elements less than x w   E: elements equal x L w   G: elements greater than x n   Search: depending on k, either answer is in E, or we need to recur in either L or G © 2014 Goodrich, Tamassia, Goldwasser Selection E k |L|+|E| k’ = k - |L| - |E| |L| x } (y) return L, E, G Selection 4 2 Selection 3/29/14 21:22 Quick-Select Visualization ! An execution of quick-select can be visualized by a recursion path n   Each node represents a recursive call of quick-select, and stores k and the remaining sequence k=5, S=(7 4 9 3 2 6 5 1 8) k=2, S=(7 4 9 6 5 8) k=2, S=(7 4 6 5) k=1, S=(7 6 5) 5 © 2014 Goodrich, Tamassia, Goldwasser Selection 5 Expected Running Time ! Consider a recursive call of quick-select on a sequence of size s n   n   Good call: the sizes of L and G are each less than 3s/4 Bad call: one of L and G has size greater than 3s/4 7 2 9 43 7 6 1 7 2 9 43 7 6 19 2 4 3 1 7 9 7 1 → 1 1 7294376 Good call Bad call ! A call is good with probability 1/2 n   1/2 of the possible pivots cause good calls: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Bad pivots © 2014 Goodrich, Tamassia, Goldwasser Good pivots Selection Bad .

• Cơ sở dữ liệu
• Data structures
• Data structures and algorithms
• Computer science
• Design of data structures
• Algorithms in Java
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming