1. Problem 6.2, p.265: In section 6.2, prior to executingalgorithm PRAM LINKED LIST PREFIX, those processors involved in performing the prefix computation over L candetermine 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 analternative termination condition for the algorithm.
2. Give an algorithm for numbering the nodes of a tree in inordertraversal sequence. The assumptions of the Euler Touralgorithm hold. Also, assume that if there are k children of anode v, then v is visited after its first child and its descendantsare 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?