Newsgroups: ut.theory
Path: utzoo!utgpu!jarvis.csri.toronto.edu!neat.ai.toronto.edu!bmkapron
From: bmkapron@ai.utoronto.ca (Bruce Kapron)
Subject: Student Seminar
Message-ID: <88Nov4.103634est.1629@neat.ai.toronto.edu>
Organization: Department of Computer Science, University of Toronto
Distribution: ut
Date: Fri, 4 Nov 88 10:36:21 EST

Time: Tuesday, November 8, 2pm EST

Location: University College Room 257

Speaker: Naomi Nishimura

Title: Parallel Computation on 2-3 Trees

Summary:

This talk will be based on a paper by Paul, Vishkin, and Wagener, and will
touch upon issues concerning data structures and parallel algorithms.  
Consider the following problem: k processors of a PRAM simultaneously 
insert, delete, or access data stored in a 2-3 tree.  Clearly, if we allow
concurrent read, then simultaneous access can be done in time log(number of
data items).  But what about insertion and deletion, and what about other
PRAM models?

We will solve this problem, relying on the paper only where necessary.
This means that I will guide the discussion, as needed, and you will figure
out the results.  No previous experience with either 2-3 trees or PRAMs is
necessary.