Now showing items 1-3 of 3
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 ...