Use the information given to answer parts a, b, and c below. Be thorough in your explanation to reach a logical conclusion.

The remaining problems center around a circuit {or network) to compute Andi-l, #0. We will, for the most part, use + {integer addition) as the operation [although the underlying principle applies to any associative binary operation, it]. Figure illustrates one method for computing AccA, +}, where A is a list of integers and + is integer addition. The network in Figure uses 3 adders and takes 3 units of time; 1 3 E 10 1'0 3 Figure l: The gure shows a circuit to compute Acc[A, +), where A : (l, 2, 3, 4,) and + is integer addition. Each box with a + in it represents an adder that takes two inputs {incoming arrows} and produces one output [their sum] which is often used in two places (shown as two outgoing arrows from the box}. The values in red show the inputs, intermediate and nals results in the network. each unit of time is the delay of an adder. This is because the lowest adder computes the rst intermediate result [3), only after which the second adder computes result 6, and nally using the intermediate result 6 the last adder computes 10. a) Draw similar figures to illustrate the computation of Acc ((1, 2), +) and Acc ((1, 2, 3, 4, 5), +). Write the input, output and intermediate values to show that the circuit works cor- rectly. 20 points b ) Prove by induction on n 2 2 that the above method for computing Acc ((a; : 1 1. We will call this network Net(k). For k = 1 (or n = 2), Net(1) is shown in Figure 2. For k > 1, let the input be A = a; : 1