A brief introduction to randomized algorithms In the aflalysis of algorithms, at least three different measures of performance can be used: the best case, the worst case, and the average case. 2 For instance, the worst case run time of Hoare's quicksort is O(n ), whereas its average case run time is only O( n log n).

1 Optimal Bounds on Tail Probabilities: A Study of an Approach.- 1.1 Introduction.- 1.2 Bounding Tail Probabilities with the Laplace Transform.- 1.3 When only the Mean is given: The Hoeffding Bound.- 1.4 When the Mean and the Variance are given: A Simple Proof of the Bennett Bound.- 1.5 When the First n Moments are Given: A Glimpse of the General Theory.- 1.6 An Application: Improved Bounds for the List Update Problem.- References.- 2 Parallelism in Comparison Problems.- 2.1 Introduction.- 2.2 Selection.- 2.3 Merging.- 2.4 Sorting.- 2.5 Conclusions.- References.- 3 Random Sampling.- 3.1 Introduction.- 3.2 Preliminaries.- 3.3 Partitioning I: Sorting.- 3.4 Partitioning II: List Ranking.- 3.5 Pruning I: Selection.- 3.6 Pruning II: Row maxima of monotone matrices.- 3.7 Pruning III: Graph Connected Components.- 3.8 Other examples.- 3.5 Bibliographic Notes.- References.- 4 Randomized Algorithms on the Mesh.- 4.1 Introduction.- 4.2 Preliminaries.- 4.3 Routing on the mesh.- 4.4 Sorting on the mesh.- 4.5 Selection on the mesh.- References.- 5 Efficient Randomized Algorithms.- 5.1 Introduction.- 5.2 Preliminaries.- 5.3 Randomized Routing.- 5.4 Randomized Selection.- 5.5 Randomized Sorting.- 5.6 Randomized PRAM Emulation.- 5.7 Selection and Sorting Schemes for Processing Large Distributed Files.- 5.8 Conclusions.- References.- 6 Ultrafast Randomized Parallel Algorithms for Spanning Forests.- 6.1 Introduction.- 6.2 Uitrafast Parallel Algorithms.- 6.3 Dense Instances.- 6.4 Ultrafast Algorithms for Spanning Forests.- 6.5 Open Problems and Further Research.- References.- 7 Parallel Randomized Techniques for Some Fundamental Geometric Problems.- 7.1 Introduction.- 7.2 Preliminaries and Definitions.- 7.3 The Use of Randomization in Computational Geometry.- 7.4 Applications to Fundamental Geometric Problems.- 7.5 Summary.- References.- 8 Capturing the Connectivity of High-Dimensional Geometric Spaces.- 8.1 Introduction.- 8.2 Basic Probabilistic Roadmap Planner.- 8.3 Other Sampling Strategies.- 8.4 Roadmap Coverage.- 8.5 Roadmap Connectedness.- 8.6 Current and Future Work.- Appendix: A. Proof of Theorem 1.- Appendix: B. Proof of Theorem 2.- Appendix: C. Proof of Theorem 3.- Appendix: D. Proof of Theorem 4.- References.- 9 Randomized Parallel Prefetching and Buffer Management.- 9.1 Introduction.- 9.2 Definitions.- 9.3 Read-Once Reference Strings.- 9.4 Read-Many Reference Strings.- 9.5 Concluding Remarks.- References.- 10 DFA Problems.- 10.1 Introduction.- 10.2 Membership Problem.- 10.3 Containment and Equivalence Problems.- 10.4 Ranking and Related Problems.- 10.5 Coarsest Partition Problems.- 10.6 Automata Testing Problems.- 10.7 Conversion from Regular Expression to NFA.- 10.8 Applications.- 10.9 Open Problems.- References.- 11 LAPACK90.- 11.1 Introduction.- 11.2 Interface Blocks for LAPACK 77.- 11.3 Interface Blocks for LAPACK 90.- 11.4 Code of LAPACK90 Routines.- 11.5 LAPACK90 Documentation.- 11.6 LAPACK90 Test Programs.- 11.7 LAPACK90 User Callable Routines.- References.- Appendix: A, Generic Interfaces.- A.1 LAPACK77 Generic Interface Blocks.- A.2 LAPACK90 Generic Interface Blocks.- Appendix: B, Interface Subroutines.- B.1 LA_GESV and LA_GETRI subroutines.- B.2 Auxiliary Routines.- Appendix: C.- C.1 Documentation of LA_GESV.- Appendix: D.- D.1 The LA_GESV test results.- Appendix: E.- E.1 LAPACK90 User Callable Routines.