Xref: utzoo ont.events:1492 uw.talks:165 uw.cs.grad:144
Path: utzoo!utgpu!watserv1!watmath!maytag!water!wlrush
From: wlrush@water.waterloo.edu (Wenchantress Wench Wendall)
Newsgroups: ont.events,uw.talks,uw.cs.grad
Subject: ALGORITHMS SEMINAR
Keywords: Dr. G. Plaxton, MIT Comp. Sci. Lab, will speak on
Message-ID: <3016@water.waterloo.edu>
Date: 21 Feb 90 20:07:54 GMT
Distribution: ont
Organization: U of Waterloo, Ontario
Lines: 35

``Deterministic Sorting in Nearly Logarithmic Time on 
the Hypercube and Related Computers.''



DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

ALGORITHMS SEMINAR

                    -Monday, February 26, 1990

Dr.  G. Plaxton, MIT Computer Science Lab will speak on
``Deterministic  Sorting  In Nearly Logarithmic Time on
the Hypercube and Related Computers.''

TIME:                 3:30 p.m.

ROOM:                 DC 1304

ABSTRACT

This   talk   will   present  a  deterministic  sorting
algorithm, called Sharesort, that sorts n records on an
n   processor   hypercube,  shuffle-exchange  or  cube-
                                   2
connected cycles in O(logn(loglogn) ) time in the worst
case.  The algorithm requires only a constant amount of
storage   at  each  processor.   The  fastest  previous
deterministic  algorithm  for  this problem was bitonic
                                      2
sort [Batcher~68], which runs in O(log n) time.

Joint work with Bob Cypher of IBM Almaden.