4. (16 points) In class, we discussed the Russian Peasant Multiplication (RPM) algorithm. The pseudocode implementation of this algorithm is: procedure RPM(m : real number; n : positive integer) 1. total := 0 2. a := m 3. b := n 4. while b > 1 5. if (b mod 2 = 1) then total := total + a 6. a := 2 a 7. b := b div 2 8. return total + a

(a) Trace (i.e. walk through) an example of the operation of this algorithm when m = 208 and n = 41. Note: for full credit, Include enough work to trace the execution of the algorithm on these inputs. Clearly label the output of the algorithm in your answer.)

(b) Convert m = 208 and n = 41 to binary notation. Note: include the calculations you use in support of your answer. You need not write an explanation of the conversion for this question.

(c) Multiply m = 208 and n = 41 using the usual school algorithm for long multiplication (but in base 2 instead of decimal). Note: include the calculations you use in support of your answer.

(d) Convert your answer from part (c) back to decimal, and compare to part (a).

Note: include the calculations you use in support of your answer. You need not write an explanation of the conversion for this question.

(e) Explain how the steps in parts (a) and parts (c) correspond to one another. For full credit, the explanation must use grammatically correct, complete sentences but may be short. Make specific reference to RPM (either its English-language description from class or the pseudocode above) and to the usual-school-algorithm for long multiplication.