Homework 10 Solution

CS409 - Spring 2000

Due: Thursday, Apr 20

1. (10 pts) Consider a binary counter with operations Increment and Clear.  Increment adds one to the current value of the counter; it takes time proportional to the number of binary digits that are changed.  Clear resets the counter to zero.
   1. Assume that only Increment operations are used.  Show that the amortized time per operation is O(1).
      The important observation is that even though a single Increment operation can cause lots of bits to change, there is only a single 1-bit that is created; the other changes are all 1-bit into 0-bit.  We charge 2 credits for each Increment operation.  The operation pays one credit to start itself and stores the extra credit with the single 1-bit that the operation creates. The rest of the work (1-bits into 0-bits) is paid for by the credit stored with each 1-bit.  It's easy to see this scheme provides enough credits to complete the operation, so the amortized time per operations is O(1).
   2. Assume that both Increment and Clear operations are used.  Describe how to implement Clear and show that the amortized time per operation is still O(1). (Hint: Keep track of the highest-order bit that is set to 1.)
      The hint tells us how to implement the Clear operation: we just start at the highest-order 1-bit and move right, setting all bits to 0.  Now we need to show that we still need just a constant number of bits charged per operation.  We charge 3 credits for each increment operation and one credit for each Clear operation. The first two Increment credits are used, as in the text, to set a bit to 1 and to store a credit with this 1; the remaining credit is stored with the counter.  The number of credits stored with the counter is always equal to the current value of the counter (which is considerably more than the length of the counter --- the amount of credit that we really need to do a Clear).  Thus there are always sufficiently many credits available (stored with the counter) to accomplish a Clear-operation.  Since O(1) credits are charged for each operation and since there are always enough credits available to accomplish these operations, the amortized time per operation is O(1).

    

2. (10 pts) Show that Sorting reduces to EMST in linear time.  Sorting Problem: Given n numbers, return them in sorted order. EMST Problem:  Given n points in the plane, find the Minimum Spanning Tree of the points; the cost of connecting a pair of points is equal to the Euclidean distance (i.e., the standard, everyday distance) between the points.   (Hint: Think about how we showed that Sorting reduces to Convex Hull.)
   We have to show how a Sorting Problem can be solved by making use of a subroutine call to an (imaginary) algorithm for solving EMST.  Suppose we are given a sorting problem consisting of n numbers.  We take each number and map it to the corresponding point (in the plane) on the x-axis.  Now we use these points as input to the EMST algorithm.  Observe that the Minimum Spanning Tree for points along a line consists of segments connecting adjacent points.  Assuming the the EMST is reported to us as an undirected graph G, we can find the leftmost point in linear time.  We can then use start from this leftmost point to find the remaining points in order from smallest to largest.  We then report the x-coordinate of this sorted list of points to produce the sorted list of our original numbers.

    

3. (20 pts) We need an ADT with the operations Insert, GetMax (report the maximum item and delete it from the data structure), and ReportMin (report the minimum value without deleting it from the data structure).  For each set of requirements listed below, describe a data structure for the ADT that fits the requirements or show that there is no such data structure.  (Note: n is the number of items currently held in the data structure.)
   1. All operations take worst-case time O(log n).
      One way to do this is to use a balanced tree (e.g., a red-black tree).  It can also be done by using a max-heap with an extra word to store the current minimum.
   2. GetMax and ReportMin each take worst-case time O(1).
      A sorted array (sorted from smallest to largest) works here.  Insert is slow, O(n).
   3. Insert and GetMax each take worst-case time O(1).
      There is no data structure that can do this (assuming that comparisons are being used).  If there were such a data structure then we could use it to sort n numbers in O(n) time by inserting all the numbers and the repeatedly using GetMax.
   4. Insert and ReportMin each take worst-case time O(1).
      An unsorted linked-list (or array) works here, but we need to use an extra word to keep track of the current minimum item.  For Insert, we update the current minimum if necessary and then put the new item on the end of the list.  For ReportMin, we report the current minimum.  For GetMax, we have to search through the whole list (O(n) time).  Note that we can't just use an extra word to keep track of the current maximum item.  Such an extra word would allow us to report the current max in O(1) time, but we would then have to update the current max value and this would require a search.