Fast Parallel Algorithms for Basic Problems

<p>Parallel processing is one of the most active research areas these days. We are interested in one aspect of parallel processing, i.e. the design and analysis of parallel algorithms. Here, we focus on non-numerical parallel algorithms for basic combinatorial problems, such as data structures, selection, searching, merging and sorting. The purposes of studying these types of problems are to obtain basic building blocks which will be useful in solving complex problems, and to develop fundamental algorithmic techniques.</p> <p>In this thesis, we study the following problems: priority queues, multiple search and multiple selection, and reconstruction of a binary tree from its traversals. The research on priority queue was motivated by its various applications. The purpose of studying multiple search and multiple selection is to explore the relationships between four of the most fundamental problems in algorithm design, that is, selection, searching, merging and sorting; while our parallel solutions can be used as subroutines in algorithms for other problems. The research on the last problem, reconstruction of a binary tree from its traversals, was stimulated by a challenge proposed in a recent paper by Berkman et al. ("Highly Parallelizable Problems," STOC 89) to design doubly logarithmic time optimal parallel algorithms because a remarkably small number of such parallel algorithms exist.</p>

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Year dc:date.available

1991

Author dc:creator

• Wen, Zhaofang

Contributors dc:contributor

• C. Michael Overstreet
• Stephan Olariu
• Chester E. Grosch
• James Schwing
• Przemyslaw Bogacki

• Parallel algorithms
• Basic problems
• Fast
• Parallel processing
• Computer Sciences

Statement dc:rights

• <p>In Copyright. URI: <a href="http://rightsstatements.org/vocab/InC/1.0/">http://rightsstatements.org/vocab/InC/1.0/</a> This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).</p>

Repository record dc:identifier

https://digitalcommons.odu.edu/computerscience_etds/120

OAI identifier oai:identifier

oai:digitalcommons.odu.edu:computerscience_etds-1119