Efficient Linked List Ranking Algorithms and Parentheses Matching as a New Strategy for Parallel Algorithm Design Page: 3
The following text was automatically extracted from the image on this page using optical character recognition software:
Halverson, Ranette Hudson, Efficient Linked List Ranking Algorithms and Paren-
theses Matching as a New Strategy for Parallel Algorithm Design, Doctor of Philos-
ophy (Computer Science), December 1993,118 pp., 9 tables, 24 figures, bibliography,
The goal of a parallel algorithm is to solve a single problem using multiple pro-
cessors working together and to do so in an efficient manner. In this regard, there is
a need to categorize strategies in order to solve broad classes of problems with sim-
ilar structures and requirements. In this dissertation, two parallel algorithm design
strategies are considered: linked list ranking and parentheses matching.
Deterministic and randomized linked list ranking algorithms are presented for
the exclusive-read exclusive-write (EREW) parallel random access machine (PRAM)
model. They are based on a technique unlike the traditional reduction method. The
randomized algorithm is work-optimal, and, although the deterministic is not, the
technique is quite simple in comparison to previously proposed algorithms and has
the advantage of small constant factors in terms of time and space requirements.
Another contribution of this dissertation is the establishment of parentheses match-
ing as a general strategy for designing efficient parallel algorithms. This is accom-
plished through the development of a class of tree related algorithms for the PRAM
model which are solved using parentheses matching as a major component. The prob-
lems solved include the heights and extreme values of the nodes of a tree, the least
common ancestor problem, inorder traversal of a tree, tree contraction, and balancing
binary trees. Finally, a hypercube implementation for parentheses matching and its
application to the nearest enclosing parentheses problem are presented .
Here’s what’s next.
This dissertation can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Dissertation.
Halverson, Ranette Hudson. Efficient Linked List Ranking Algorithms and Parentheses Matching as a New Strategy for Parallel Algorithm Design, dissertation, December 1993; Denton, Texas. (digital.library.unt.edu/ark:/67531/metadc278153/m1/3/: accessed February 21, 2019), University of North Texas Libraries, Digital Library, digital.library.unt.edu; .