Titlebook: Space-Efficient Data Structures, Streams, and Algorithms; Papers in Honor of J Andrej Brodnik,Alejandro López-Ortiz,Alfredo Viola Book 2013

微粒

On Generalized Comparison-Based Sorting Problems,production and sorting under partial information. We emphasize the complementarity of the two problems and the common aspects of the algorithms. We also include open questions on two other related problems, namely partial order identification and sorting with forbidden comparisons.

Vertebra

,A Survey of the Game “Lights Out!”,l and the lights of its rectilinear adjacent neighbors. Given an initial configuration of lights, some on and some off, the goal of the game is to switch all lights off. The game can be generalized to arbitrary graphs instead of a grid. . has been studied independently by three different communities

一个搅动不安

Random Access to High-Order Entropy Compressed Text,ntropy of the string, which is a lower bound on the compression achievable with text compressors based on contexts, and (.) constant-time access is still provided to the string as if it was uncompressed. This is obviously better than decompressing (a large portion of) the whole string each time a ra

BLOT

Succinct and Implicit Data Structures for Computational Geometry,two-dimensional geometric data set consisting of . elements, these structures typically require .(.), close to .(.) or . words of space; while they support efficient queries, their storage costs are often much larger than the space required to encode the given data. As modern applications often proc

laceration

In Pursuit of the Dynamic Optimality Conjecture, constant factor as any offline rotation-based search tree algorithm on every sufficiently long sequence—any binary search tree algorithm that has this property is said to be dynamically optimal. However, currently neither splay trees nor any other tree algorithm is known to be dynamically optimal.

Dri727

anachronistic

大骂

A Survey of Data Structures in the Bitprobe Model,udied later in the context of retrieval problems by Elias and Flower [15], and generalized by Yao [50] to the cell probe model. In the bitprobe model, we concern ourselves with the number of bit accesses or bit flips that occur during a computation. We wish to analyze the trade-off between the space

CON

critic

Book 2013In celebration of his 66th birthday the colloquium "Conference on Space Efficient Data Structures, Streams and Algorithms" was held in Waterloo, ON, Canada, during August 15-16, 2013. The articles presented herein cover some of the main topics of Ian‘s research interests. Together they give a good o