Lecture Notes on Bucket Algorithms by Luc Devroye
  

Lecture Notes on Bucket Algorithms

Written by Luc Devroye
Illustrated by
Part of the Progress in Computer Science and Applied Logic Series

Synopsis

Lecture Notes on Bucket Algorithms by Luc Devroye

Hashing algorithms scramble data and create pseudo-uniform data distribu- tions. Bucket algorithms operate on raw untransformed data which are parti- tioned Into groups according to membership In equl-slzed d-dlmenslonal hyperrec- tangles, called cells or buckets. The bucket data structure Is rather sensitive to the distribution of the data. In these lecture notes, we attempt to explain the connection between the expected time of various bucket algorithms and the dis- tribution of the data. The results are Illustrated on standard searching, sorting and selection problems, as well as on a variety of problems In computational geometry and operations research. The notes grew partially from a graduate course on probability theory In computer science. I wish to thank Elizabeth Van Gulick for her help with the manuscript, and David Avis, Hanna AYukawa, Vasek Chvatal, Beatrice Devroye, Hossam EI Glndy, Duncan McCallum, Magda McCallum, Godfrled Toussaint and Sue Whltesldes for making the School of Computer Science at McGill University such an enjoyable place. The work was supported by NSERC Grant A3456 and by FCAC Grant EQ-1679. INTRODUCTION 1 INTRODUCTION It Is not a secret that methods based upon the truncation of data have good expected time performance. For example, for nice distributions of the data, searching Is often better done via a hashing data structure Instead of via a search tree. The speed one observes In practice Is due to the fact that the truncation operation Is a constant time operation.

About the Author

Other Formats

Book Info

Format

Paperback
148 pages

Author

Luc Devroye
More books by Luc Devroye

Publisher

Birkhauser Boston Inc

Publication date

1st January 1985

ISBN

9780817633288


I love finding new books to read. My mummy and me look at the new ones coming out. I have written reviews of some of them!

Jessica Cobbin – age 7

I love ‘LoveReading 4 kids’ because they let you read and learn things you’d never dreamed of learning before.

Emily Horncastle – age 11

Lovereading4kids is great, we get books really early never late. We love to read and review, and think you would like it too. The excitement

Jasmine Harris-Hart, age 12

At @HHSHaringey we love @lovereading4kids because our pupils can practice reviewing & get free upcoming books before anyone else!

Helen Swinyard – Heartlands High

I think Lovereading4kids is an amazing company because of the friendly staff and the fabulous chance to read great books before publication.

Adam Graham

I love Lovereading because I often never know what to read and this helps you find a good book. I have recommended this to many people.

Shannon-Louise Masters – age 15

We love Lovereading as my 5 year old loves to read new books before anyone else has a chance, she says it makes reading exciting!

Tracey Chorley

You give me age appropriate ideas of books I can read and buy for the children and find out what other children their age think of them too.

Katie Lonsdale
Lovereading

Lovereading 4 schools
****