Xref: utzoo ont.events:1432 uw.talks:118 uw.cs.grad:105
Path: utzoo!utgpu!watserv1!watcgl!rmvale
From: rmvale@watcgl.waterloo.edu (Ruth Vale)
Newsgroups: ont.events,uw.talks,uw.cs.grad
Subject: Re: ICR Wednesday Colloquium
Keywords: parallel algorithms shared memory cells
Message-ID: <12956@watcgl.waterloo.edu>
Date: 15 Jan 90 16:13:07 GMT
References: <12955@watcgl.waterloo.edu>
Organization: U of Waterloo, Ontario
Lines: 24

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.