Overview

The technique of randomization has been employed to solve numerous prob­ lems of computing both sequentially and in parallel. Examples of randomized algorithms that are asymptotically better than their deterministic counterparts in solving various fundamental problems abound. Randomized algorithms have the advantages of simplicity and better performance both in theory and often is a collection of articles written by renowned experts in practice. This book in the area of randomized parallel computing. A brief introduction to randomized algorithms In the analysis of algorithms, at least three different measures of performance can be used: the best case, the worst case, and the average case. Often, the average case run time of an algorithm is much smaller than the worst 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(nlogn). The average case analysis is conducted with an assumption on the input space. The assumption made to arrive at the O(n logn) average run time for quicksort is that each input permutation is equally likely. Clearly, any average case analysis is only as good as how valid the assumption made on the input space is. Randomized algorithms achieve superior performances without making any assumptions on the inputs by making coin flips within the algorithm. Any analysis done of randomized algorithms will be valid for all possible inputs.

Full Product Details

Author:   Sanguthevar Rajasekaran ,  Panos M. Pardalos ,  J.H. Reif ,  José Rolim
Publisher:   Springer-Verlag New York Inc.
Imprint:   Springer-Verlag New York Inc.
Edition:   Softcover reprint of the original 1st ed. 2001
Volume:   9
Dimensions:   Width: 15.50cm , Height: 5.60cm , Length: 23.50cm
Weight:   1.576kg
ISBN:  

9781461348863

ISBN 10:   1461348862
Pages:   996
Publication Date:   07 December 2013
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   Manufactured on demand  
We will order this item for you from a manufactured on demand supplier.

Table of Contents

Preface. Contributing Authors. Volume I. 1. Random Sampling: Sorting and Selection; D. Krizanc, S. Rajasekaran. 2. Simplified Analysis of Randomized Algorithms for Searching, Sorting, and Selection; M.T. Goodrich, R. Tamassia. 3. Concentration of Measure for Randomized Algorithms: Techniques and Analysis; D. Dubhashi, S. Sen. 4. Randomization in Graph Optimization Problems: A Survey; D.R. Karger. 5. The Delay Sequence Argument; A. Ranade. 6. Randomized Algorithms for Geometric Optimization Problems; P.K. Agarwal, S. Sen. 7. Randomized Geometry Algorithms for Coarse Grained Parallel Computers; Xiaotie Deng. 8. A Randomized Approach to Robot Path Planning Based on Lazy Evaluation; R. Bohlin, L.E. Kavraki. 9. The Power of Two Random Choices: A Survey of Techniques and Results; M. Mitzenmacher, A.W. Richa, R. Sitaraman. 10. Randomized Techniques for Modelling Faults and Achieving Robust Computing; S.E. Nikoletseas, P.G. Spirakis. 11. Randomized Communication in Radio Networks; B.S. Chlebus. Index. Preface. Contributing Authors. Volume II. 12. A Guide to Concentration Bounds; J. Díaz, J. Petit, M. Serna. 13. Bounded Error Probabilistic Finite State Automata; A. Condon. 14. Communication Protocols - An Exemplary Study of the Power of Randomness; J. Hromkovic. 15. Property Testing; D. Ron. 16. The Random Projection Method; S. Vempala. 17. Error Estimates for Indirect Measurements: Randomized vs. Deterministic Algorithms for `Black-Box' Programs; V.Kreinovich, R. Trejo. 18. Derandomization in Combinatorial Optimization; A. Srivastav. 19. Derandomizing Complexity Classes; P.B. Miltersen. Index.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions