Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Bounded capacity priority queues
Atkinson M., Tulley D. Theoretical Computer Science182 (1-2):145-157,1997.Type:Article
Date Reviewed: Jun 1 1998

Using the language of set algebra (such as cosets) and automata (for example, computation for a string manipulation), the authors consider the number of allowable orderings possible for a string that is processed through a limited buffered priority queue. In particular, they show that over all n strings of uniquely ordered characters, with a buffer size of 2, the number of possible output strings can be determined in O ( n2 ). They also show that, if the string is binary-valued, one can use a formula found in de Bruijn et al. [1] to calculate the number of possible output sequences in O(size of buffer).

Reviewer:  T. Brown Review #: CR121255 (9806-0428)
1) de Bruijn, N. G.; Knuth, D. E.; and Rice, S. O. The average height of planted plane trees. In Graph Theory and Computing, R. C. Read, Ed., Academic Press, New York, 1972, 15–22. See <CR> 14, 5 (May 1973), Rev. 25,093.
Bookmark and Share
 
Lists, Stacks, And Queues (E.1 ... )
 
 
Permutations And Combinations (G.2.1 ... )
 
 
Type Structure (F.3.3 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Lists, Stacks, And Queues": Date
A priority queue for the all pairs shortest path problem
Moffat A., Takaoka T. Information Processing Letters 18(4): 189-193, 1984. Type: Article
Mar 1 1985
Amortized efficiency of list update and paging rules
Sleator D., Tarjan R. (ed) Communications of the ACM 28(2): 202-208, 1985. Type: Article
Nov 1 1985
Self-organizing search lists using probabilistic back-pointers
Hester J., Hirschberg D. Communications of the ACM 30(12): 1074-1079, 1987. Type: Article
Oct 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy