1. Graded Problem (Page limit: 1 sheet; 2 sides) In the lecture for Union-Find we discussed an accounting trick that gives some credit in a global account that paid for the per step cost when a node on a path has parent with rank at a higher bracket. Here is a problem that can be solved in a similar manner (although arguably simpler. You have a digital counter (you can assume it has an unbounded number of digits), where each digit records a symbol in D = {0, 1, . . . , 9). The counter holds a digital number in the usual sense. A stream of digits come in in sequence al, a2, as, . . . an E D. Your digital counter at time step t will record the prefix sum 1 ai in the counter. The cost per each addition from 1-1 ai to ait at-1 ai is one plus the number of "carry" steps the addition causes. Show that the total cost of these n addition operations is O(n) What if a1, a2, a3,...an E{-1, 1j? Show that it is possible that your digital counter is "trashing", that is, for a suitable sequence of n inputs from {-1,1), the digital counter costs more than O(n) asymptotically What is an upper bound of the total cost in this case? Now suppose you can afford two digital counters. Design an algorithm that uses these two digital counters jointly to handle the sequence of n operations adding or subtracting digits, i.e., where a1, a2, a3,... an D, so that the total cost is O(n). In an earlier homework (hw0) we have seen that every integer (positive, negative, or zero) can be written uniquely in the form 000 bigi, where each bi E {0, 1,-1} and, bi0 for only finitely many i > 0. Use this knowledge to build a "ternary" counter. Write a pseudocode for the operations of PLUS 1 and MINUS 1 in in this "ternary" counter system