this is all that was given.
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- 10,1,...,91. The counter holds a digital number in the usual sense. A stream of digits come in in sequence ai, a2, a3, . . . an E D. Your digital counter at time step t will record the prefix sum ' i in the counter, The cost per each addition from of "carry" steps the addition causes i ai to 1-1 ait at--i a, is one plus the number Show that the total cost of these n addition operations is O(n) What if a1, a2,a3, ...an E-1, 13? 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, ie., where a1, a2, a3 " an E 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 writtern uniquely in the form _0b,31, where each bi E {01,-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. 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- 10,1,...,91. The counter holds a digital number in the usual sense. A stream of digits come in in sequence ai, a2, a3, . . . an E D. Your digital counter at time step t will record the prefix sum ' i in the counter, The cost per each addition from of "carry" steps the addition causes i ai to 1-1 ait at--i a, is one plus the number Show that the total cost of these n addition operations is O(n) What if a1, a2,a3, ...an E-1, 13? 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, ie., where a1, a2, a3 " an E 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 writtern uniquely in the form _0b,31, where each bi E {01,-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
