Now showing items 1-5 of 5
The Maximum of a Random Walk and Its Application to Rectangle Packing
Let S0,...,Sn be a symmetric random walk that starts at the origin (S0 = 0), and takes steps uniformly distributed on [-1,+1]. We study the large-n behavior of the expected maximum excursion and prove the estimate$$ \exd ...
Matrix Transposition on a Mesh with Blocking Transmissions
A time-optimal procedure to transpose in situ a matrix stored over a distributed memory 2-dimensional mesh-connected parallel computer is shown. The matrix need not be square. Only nearest-neighbor blocking communications ...
Saddle points in random matrices: analysis of Knuth search algorithms
In this note we present an analysis of algorithms for finding saddle points in a random matrix, presented by Donald E. Knuth as exercise 1.3.2-12 in The Art of Computer Programming. We estimate the average computing costs ...
The List Update ProblemImproved Bounds for the Counter Scheme
We consider the problem of dynamic reorganization of a linear list, where requests for the elements are generated randomly with fixed, unknown probabilities. The objective is to obtain the smallest expected cost per access. ...
Efficient Reorganization of Binary Search Trees
We consider the problem of maintaining a binary search tree that minimizes the average access cost needed to satisfy randomly generated requests. We analyze scenarios in which the accesses are generated according to a ...