Publication Details
Title: On the Average Case Complexity of Parallel Sublist Selection
Author: G. Pucci and W. Zimmerman
Group: ICSI Technical Reports
Date: March 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-023.pdf
Overview:
The "Sublist Selection Problem" (SSP) is the following: Given an input list of nodes labeled True or False, extract the sublist of nodes labeled True. This paper analyzes the average case complexity of a parallel algorithm that solves SSP on the PRAM model of computation. The algorithm is based on the well-known "recursive doubling" technique. Doubly logarithmic upper and lower bounds are derived for the average number of iterations needed to produce the output list, under the assumption that all the nodes of the input list are marked False with prabability p, independently of the other nodes. Finally, the exact number of iterations (up to lower order terms) is established in the case that the input list is drawn from the uniform distribution over all possible labellings.
Bibliographic Information:
ICSI Technical Report TR-91-023
Bibliographic Reference:
G. Pucci and W. Zimmerman. On the Average Case Complexity of Parallel Sublist Selection. ICSI Technical Report TR-91-023, March 1991
Author: G. Pucci and W. Zimmerman
Group: ICSI Technical Reports
Date: March 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-023.pdf
Overview:
The "Sublist Selection Problem" (SSP) is the following: Given an input list of nodes labeled True or False, extract the sublist of nodes labeled True. This paper analyzes the average case complexity of a parallel algorithm that solves SSP on the PRAM model of computation. The algorithm is based on the well-known "recursive doubling" technique. Doubly logarithmic upper and lower bounds are derived for the average number of iterations needed to produce the output list, under the assumption that all the nodes of the input list are marked False with prabability p, independently of the other nodes. Finally, the exact number of iterations (up to lower order terms) is established in the case that the input list is drawn from the uniform distribution over all possible labellings.
Bibliographic Information:
ICSI Technical Report TR-91-023
Bibliographic Reference:
G. Pucci and W. Zimmerman. On the Average Case Complexity of Parallel Sublist Selection. ICSI Technical Report TR-91-023, March 1991