Parallel Algorithms
AskDrRene
hw_5.docxR. L. Hendrix
February 15, 2016
CSC 8530
HW 5
1. Problem 6.2, p.265: In section 6.2, prior to executing algorithm PRAM LINKED LIST PREFIX, those processors involved in performing the prefix computation over L can determine their number (and hence the number of nodes in L) by writing a 1 in a location size of memory, using a SUM CW. Discuss how this information can be used to provide an alternative termination condition for the algorithm.
2. Give an algorithm for numbering the nodes of a tree in inorder traversal sequence. The assumptions of the Euler Tour algorithm hold. Also, assume that if there are k children of a node v, then v is visited after its first child and its descendants are visited.
3. Does a (d,ε)- expander graph have to be a regular graph?
4. The sorting-by-splitting circuit seems to have feedback to a parent node. Does this violate the combinational circuit rule?
