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 ...
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. ...
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 ...
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 ...