rmvale@watcgl.waterloo.edu (Ruth Vale) (01/16/90)
In article <12955@watcgl.waterloo.edu>, rmvale@watcgl.waterloo.edu (Ruth Vale) writes:
ICR Colloquium
Dr. Prabhakar Ragde
Department of Computer Science
University of Waterloo
Wednesday, January 17, l990
3:30 p.m.
Davis Centre, Room l302
The Parallel Simplicity of Compaction and Chaining
The PRAM, a synchronous shared-memory parallel machine with
concurrent access to shared memory cells, is widely used for the
design of parallel algorithms. In this talk, we consider the
situation where data are scattered sparsely in a large array.
we will see how to approximately compact the data in constant time
using a linear number of processors. This leads to an optimal
algorithm for exact compression. We will also see how to arrange
the data in a linked list in not-quite-constant time. This talk
is self-contained.
Everyone is welcome. Refreshments served.