EFFICIENT LINKED LIST RANKING ALGORITHMS AND PARENTHESES MATCHING AS A NEW STRATEGY FOR PARALLEL ALGORITHM DESIGN

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