Homework 10

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).
   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.)

    

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.)

    

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).
   2. GetMax and ReportMin each take worst-case time O(1).
   3. Insert and GetMax each take worst-case time O(1).
   4. Insert and ReportMin each take worst-case time O(1).