Shortcuts
Top of page (Alt+0)
Page content (Alt+9)
Page menu (Alt+8)
Your browser does not support javascript, some WebOpac functionallity will not be available.
.
Default
.
PageMenu
-
Main Menu
-
Simple Search
.
Advanced Search
.
Journal Search
.
Refine Search Results
.
Preferences
.
Search Menu
Simple Search
.
Advanced Search
.
New Items Search
.
Journal Search
.
Refine Search Results
.
Bottom Menu
Help
Italian
.
English
.
German
.
New Item Menu
New Items Search
.
New Items List
.
Links
SISSA Library
.
ICTP library
.
Italian National web catalog (SBN)
.
Trieste University web catalog
.
Udine University web catalog
.
© LIBERO v6.4.1sp220816
Page content
You are here
:
Catalogue Display
Catalogue Display
Advances in Randomized Parallel Computing
.
Bookmark this Record
Catalogue Record 45945
.
.
LibraryThing
.
.
Google Books
.
.
Amazon Books
.
Catalogue Information
Catalogue Record 45945
.
Reviews
Catalogue Record 45945
.
British Library
Resolver for RSN-45945
Google Scholar
Resolver for RSN-45945
WorldCat
Resolver for RSN-45945
Catalogo Nazionale SBN
Resolver for RSN-45945
GoogleBooks
Resolver for RSN-45945
ICTP Library
Resolver for RSN-45945
.
Share Link
Jump to link
Catalogue Information
Field name
Details
Dewey Class
518.1
Title
Advances in Randomized Parallel Computing ([EBook] /) / edited by Panos M. Pardalos, Sanguthevar Rajasekaran.
Added Personal Name
Pardalos, Panos M.
editor.
Rajasekaran, Sanguthevar
editor.
Other name(s)
SpringerLink (Online service)
Publication
Boston, MA : : Springer US, , 1999.
Physical Details
XXVI, 287 p. : online resource.
Series
Combinatorial Optimization
1388-3011 ; ; 5
ISBN
9781461332824
Summary Note
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 in practice. This book is a collection of articles written by renowned experts in the area of randomized parallel computing. 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. 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( n log n). The average case analysis is conducted with an assumption on the input space. The assumption made to arrive at the O( n log n) 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 p0:.sible inputs.:
Contents note
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.
System details note
Online access to this digital book is restricted to subscription institutions through IP address (only for SISSA internal users)
Internet Site
http://dx.doi.org/10.1007/978-1-4613-3282-4
Links to Related Works
Subject References:
Algorithms
.
Computer Graphics
.
Computers
.
Mathematics
.
Microprocessors
.
Processor Architectures
.
Theory of Computation
.
Authors:
Pardalos, Panos M.
.
Rajasekaran, Sanguthevar
.
Corporate Authors:
SpringerLink (Online service)
.
Series:
Combinatorial Optimization
.
Classification:
518.1
.
.
ISBD Display
Catalogue Record 45945
.
Tag Display
Catalogue Record 45945
.
Related Works
Catalogue Record 45945
.
Marc XML
Catalogue Record 45945
.
Add Title to Basket
Catalogue Record 45945
.
Catalogue Information 45945
Beginning of record
.
Catalogue Information 45945
Top of page
.
Download Title
Catalogue Record 45945
Export
This Record
As
Labelled Format
Bibliographic Format
ISBD Format
MARC Format
MARC Binary Format
MARCXML Format
User-Defined Format:
Title
Author
Series
Publication Details
Subject
To
File
Email
Reviews
This item has not been rated.
Add a Review and/or Rating
45945
1
45945
-
2
45945
-
3
45945
-
4
45945
-
5
45945
-
Quick Search
Search for