[ont.events] UW Theory Seminar, Prof. J.H. Reif on "FLASHSORT: A Logarithmic ..."

mwang_pay (08/10/82)

               DEPARTMENT OF COMPUTER SCIENCE
               UNIVERSITY OF WATERLOO
               SEMINAR ACTIVITIES

               THEORY SEMINAR - Monday, August 16, 1982.

               Prof. John H. Reif of Harvard University  will  speak
               on "FLASHSORT: A Logarithmic Time Sort on Linear Size
               Networks."

               TIME:  3:30 PM

               ROOM:  M&C 6091A

               ABSTRACT

               We give a probabilistic algorithm for sorting on con-
               stant  valence  networks  of N nodes such as the CCC.
               We prove that for any input set  of  0(N)  keys,  the
               algorithm's execution time is greater than a constant
               time's log N with vanishingly low likelihood.   More-
               over  we show this constant factor is small, implying
               our sorting algorithm may be practically implemented.

               Note: This work was done in  collaboration  with  les
               Valiant.

                      August 10, 1982