(Solved): Problem 3 (Binary Counter) a) We perform a sequence of n increment operations on a counter. Assuming ...
Problem 3 (Binary Counter) a) We perform a sequence of n increment operations on a counter. Assuming that the running time of each increment operation is proportional to the number of flipped bits in the binary representation of the numbers, what is the total running time of this sequence? Example: incrementing from 7 to 8 is
0111-->
1000, resulting in 4 flipped bits, so the time is proportional to 4. b) What can you conclude about the amortized time of the increment operations for this counter? Problem 4 (Recursion) Describe a simple recursive algorithm that finds the average of n numbers. Draw its call tree and analyze its running time. See the notes for Lecture 9 on 9/26 regarding call trees. Hint: what is the connection between the average and the sum of n numbers?
