Algorithm Problem

The sum of n k-bit numbers can be computed by a combinational arithmetic circuit as follows.  Assume n is an exact power of 2.  the circuit consists of a complete binary tree of ripple-carry adders, in which each node in the tree adds two numbers and produces a sum which is fed to its parent.  The n/2 leaves of the tree input the n k-bit numbers, and the total sum is produced as output by the root.  Each ripple-carry adder is as small as possible while still ensuring that the sum is correctly computed.

a. What is the maximum number of bits in the sum of the n k-bit numbers?  What is the number of full adders in any ripple-carry adder at height h in the tree, where we view leaves as having height 0?
b. Give a tight asymptotic upper (big OP bound in terms of n and k on the size of this circuit (not the size of the tree).  Briefly explain your answer.
c. Give a tight asymptotic upper bound in terms of n and k on the depth of this circuit (not the depth of the tree).  Briefly explain your answer.
d. Describe a combinational circuit that computes the sum of n k-bit numbers more efficiently.  Draw a figure, if you wish.  Analyze the size and depth of your circuit.


Additional Information

Circuit Depth
As in the case of the comparison networks, we measure the propagation delay of a combinational circuit in terms of the largest number of combinational elements on any path from the inputs to the outputs. Specifically, we define the depth of a circuit, which corresponds to its worst-case “running time”, inductively in terms of the depths of its constituent wires. The depth of an input wire is 0. If a combinational element has inputs x1, x2,…, xn at depths d1, d2,…,dn respectively, then its outputs have depth max {d1, d2,…, dn}+1. The depth of a combinational element is the depth of its outputs. The depth of a combinational circuit is the maximum depth of any combinational element. Since we prohibit combinational circuits from containing cycles, the various notions of depth are well defined. If each combinational element takes constant time to compute its output values, then the worst-case propagation delay through a combinational circuit is proportional to its depth.
A combinational circuit can sometimes compute faster that its depth. Suppose that a large sub-circuit feeds into one input of a 2-input AND gate but that the other input of the AND gate has a value of 0. The output of the gate will then be 0, independent of the input being applied to the circuit, and the abstraction of depth as the “running time” of the circuit is therefore quite reasonable.


Circuit Size
Besides circuit depth, there is another resource that we typically wish to minimize when designing circuits. The size of a combinational circuit is the number of combinational elements it contains. Intuitively, circuit size corresponds to the memory space used by an algorithm. This definition of circuit size is not particularly useful for small circuits. After all, since a full adder has a constant number of inputs and outputs and computes a well-defined function, it satisfies the definition of a combinational element. A full adder built from a singe full adder combinational element therefore has size 1. In fact, according to this definition, any combinational element has size 1.

See attached file for full problem description.