Exercises

 

1. Newt Gingrich is given the job of partitioning 2n players into two teams of n players each. Each player has a numerical rating that measures how good he/she is at the game. Newt seeks to divide the players as unfairly as possible, so as to create the biggest possible talent imbalance between team A and team B. Show how Newt can do the job in time.  

2. Take as input a sequence of 2n real numbers. Design an algorithm that partitions the numbers into n pairs, with the property that the partition minimizes the maximum sum of a pair. For example, say we are given the numbers (1,3,5,9). The possible partitions are ((1,3),(5,9)), ((1,5),(3,9)), and ((1,9),(3,5)). The pair sums for these partitions are (4,14), (6,12), and (10,8). Thus the third partition has 10 as its maximum sum, which is the minimum over the three partitions.

3. Assume that we are given as input n pairs of items, where the first item is a number and the second item is one of three colors (red, blue, or yellow). Further, assume that the items are sorted by number. Give an O(n) algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.

   For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).

4. (*) The mode of a set of numbers is the number that occurs most frequently in the set. The set (4,6,2,4,3,1) has a mode of 4.  
   1. Give an efficient and correct algorithm to compute the mode of a set of n numbers.
   2. Suppose we know that there is an (unknown) element that occurs n/2+1 times in the set. Give a worst-case linear-time algorithm to find the mode. For partial credit, your algorithm may run in expected linear time.

5. Given two sets and (each of size n), and a number x, describe an algorithm for finding whether there exists a pair of elements, one from and one from , that add up to x. (For partial credit, give a algorithm for this problem.)

6. For each of the following problems, give an algorithm that finds the desired numbers within the given amount of time. To keep your answers brief, feel free to use algorithms from the book as subroutines. For the example, , 19-3 maximizes the difference, while 8-6 minimizes the difference.

   (a) Let S be an unsorted array of n integers. Give an algorithm that finds the pair that maximizes |x-y|. Your algorithm must run in O(n) worst-case time.

   (b) Let S be a sorted array of n integers. Give an algorithm that finds the pair that maximizes |x-y|. Your algorithm must run in O(1) worst-case time.

   (c) Let S be an unsorted array of n integers. Give an algorithm that finds the pair that minimizes |x-y|, for . Your algorithm must run in worst-case time.

   (d) Let S be a sorted array of n integers. Give an algorithm that finds the pair that minimizes |x-y|, for . Your algorithm must run in O(n) worst-case time.

7. (*) Describe how to modify any balanced tree data structure such that search, insert, delete, minimum, and maximum still take time each, but successor and predecessor now take O(1) time each. Which operations have to be modified to support this?
8. (*) In one of my research papers [Ski88], I give a comparison-based sorting algorithm that runs in . Given the existence of an lower bound for sorting, how can this be possible?  
9. (*) Suppose you have access to a balanced dictionary data structure, which supports each of the operations search, insert, delete, minimum, maximum, successor, and predecessor in time. Explain how to modify the insert and delete operations so they still take but now minimum and maximum take O(1) time. (Hint: think in terms of using the abstract dictionary operations, instead of mucking about with pointers and the like.)
10. (*) Mr. B. C. Dull claims to have developed a new data structure for priority queues that supports the operations Insert, Maximum, and Extract-Max, all in O(1) worst-case time. Prove that he is mistaken. (Hint: the argument does not involve a lot of gory details-just think about what this would imply about the lower bound for sorting.)

11. Use the partitioning step of Quicksort to give an algorithm that finds the median element of an array of n integers in expected O(n) time.

12. (*) You are given the task of reading in n numbers and then printing them out in sorted order. Suppose you have access to a balanced dictionary data structure, which supports each of the operations search, insert, delete, minimum, maximum, successor, and predecessor in time.
    • Explain how you can use this dictionary to sort in time using only the following abstract operations: minimum, successor, insert, search.
    • Explain how you can use this dictionary to sort in time using only the following abstract operations: minimum, insert, delete, search.
    • Explain how you can use this dictionary to sort in time using only the following abstract operations: insert and in-order traversal.

13. The running time for Quicksort depends upon both the data being sorted and the partition rule used to select the pivot. Although Quicksort is on average, certain partition rules cause Quicksort to take time if the array is already sorted.

    (a) Suppose we always pick the pivot element to be the key from the last position of the subarray. On a sorted array, does Quicksort now take , , or ?

    (b) Suppose we always pick the pivot element to be the key from the middle position of the subarray. On a sorted array, does Quicksort now take , , or ?

    (c) Suppose we always pick the pivot element to be the key of the median element of the first three keys of the subarray. (The median of three keys is the middle value, so the median of 5, 3, 8 is five.) On a sorted array, does Quicksort now take , , or ?

    (d) Suppose we always pick the pivot element to be the key of the median element of the first, last, and middle elements of the subarray. On a sorted array, does Quicksort now take , , or ?

14. (*) Given a set S of n integers and an integer T, give an algorithm to test whether k of the integers in S sum up to T.
15. (**) Design a data structure that allows one to search, insert, and delete an integer X in O(1) time (i.e. constant time, independent of the total number of integers stored). Assume that and that there are m+n units of space available for the symbol table, where m is the maximum number of integers that can be in the table at any one time. (Hint: use two arrays A[1..n] and B[1..m].) You are not allowed to initialize either A or B, as that would take O(m) or O(n) operations. This means the arrays are full of random garbage to begin with, so you must be very careful.
16. (*) Let P be a simple, but not necessarily convex, polygon and q an arbitrary point not necessarily in P. Design an efficient algorithm to find a line segment originating from q that intersects the maximum number of edges of P. In other words, if standing at point q, in what direction should you aim a gun so the bullet will go through the largest number of walls. A bullet through a vertex of P gets credit for only one wall. An algorithm is possible.
17. (**) The onion of a set of n points is the series of convex polygons that result from finding the convex hull, striping it from the point set, and repeating until no more points are left. Give an algorithm for determining the onion of a point set.