You saw in class that the standard algorithm to INCREMENT a binary counter runs in 0(1)...

 

Transcribed Image Text:

You saw in class that the standard algorithm to INCREMENT a binary counter runs in 0(1) amortized time. Now suppose we also want to support a second function called RESET, which resets all bits in the counter to zero. Here are the INCREMENT and RESET algorithms. In addition to the array B[...] of bits, we now also maintain the index of the most significant bit, in an integer variable msb. INCREMENT(B[0..∞], msb): i-0 while B[i] = 1 B[i] - 0 ii+1 B[i] - 1 if i > msb msb-i RESET(B[0..∞],msb): for i - 0 to msb B[i] - 0 msb-0 In parts (a) and (b), let n denote the number currently stored in the counter. (a) What is the worst-case running time of INCREMENT, as a function of n? (b) What is the worst-case running time of RESET, as a function of n? (c) Prove that in an arbitrary intermixed sequence of INCREMENT and RESET operations, the amortized time for each operation is 0(1). You saw in class that the standard algorithm to INCREMENT a binary counter runs in 0(1) amortized time. Now suppose we also want to support a second function called RESET, which resets all bits in the counter to zero. Here are the INCREMENT and RESET algorithms. In addition to the array B[...] of bits, we now also maintain the index of the most significant bit, in an integer variable msb. INCREMENT(B[0..∞], msb): i-0 while B[i] = 1 B[i] - 0 ii+1 B[i] - 1 if i > msb msb-i RESET(B[0..∞],msb): for i - 0 to msb B[i] - 0 msb-0 In parts (a) and (b), let n denote the number currently stored in the counter. (a) What is the worst-case running time of INCREMENT, as a function of n? (b) What is the worst-case running time of RESET, as a function of n? (c) Prove that in an arbitrary intermixed sequence of INCREMENT and RESET operations, the amortized time for each operation is 0(1). You saw in class that the standard algorithm to INCREMENT a binary counter runs in 0(1) amortized time. Now suppose we also want to support a second function called RESET, which resets all bits in the counter to zero. Here are the INCREMENT and RESET algorithms. In addition to the array B[...] of bits, we now also maintain the index of the most significant bit, in an integer variable msb. INCREMENT(B[0..∞], msb): i-0 while B[i] = 1 B[i] - 0 ii+1 B[i] - 1 if i > msb msb-i RESET(B[0..∞],msb): for i - 0 to msb B[i] - 0 msb-0 In parts (a) and (b), let n denote the number currently stored in the counter. (a) What is the worst-case running time of INCREMENT, as a function of n? (b) What is the worst-case running time of RESET, as a function of n? (c) Prove that in an arbitrary intermixed sequence of INCREMENT and RESET operations, the amortized time for each operation is 0(1).

Answer rating: 100% (QA)

Step 1 a The INCREMENT algorithm has a worstcase running time of On where n is the number currently recorded in the counter Explanation If the number ... View the full answer