• Exercise 9.1. Implement the in-place heap sort algorithm

• Exercise 9.2. Given a heap H and a key k, give an algorithm to compute all the entries in H having a key less than or equal to k. The algorithm should run in time proportional to the number of entries returned.

• Exercise 9.3. Assume that we are using a linked representation of a complete binary tree T, and an extra reference to the last node of that tree. Show how to update the reference to the last node after operations remove or insert in O(log n) time where n is the current number of nodes in T. Be sure to handle all possible cases.

• Exercise 9.4. The Bubble sort algorithm (given below) makes several passes through an array. On each pass, successive neighboring pairs are compared. If a pair is in decreasing order, its values are swapped; otherwise the values remain unchanged. Write the following two generic methods using bubble sort. The first method should sort the elements using the comparable interface, the second should use the Comparator interface.

public static < E extends Comparable < E > >
  void bubbleSort(E[] list)
public static < E > void bubbleSort(E[] list, 
              Comparator< ? super E > comparator) 

for (int k=1; k < list.length; k++){
  // performs the kth pass
  for(int i=0; i < list.length ; i++){
     if(list[i] > list[i+1]){
      swap list[i] with list[i+1];
 }}
}

• Exercise 9.5.
  Implement each of the Selection-Sort, Insertion-Sort and heap Sort algorithms using both the comparable and the comparator interfaces
  

public static < E extends Comparable < E > >
  void insertionSort(E[] list)
public static < E > void insertionSort(E[] list,
       Comparator < ? super E > comparator)

public static < E extends Comparable < E > >
  void heapSort(E[] list)
public static < E > void heapSort(E[] list,
       Comparator < ? super E > comparator)

• Exercise 9.6.
  Give an alternative implementation of the HeapPriorityQueue’s Upward and Downward methods that uses a recursion and no loop.
  
• Exercise 9.7.
  Suppose that two binary trees T1 and T2 hold entries satisfying the heap order property (but not necessarily the complete binary tree property). Implement a method for combining T1 and T2 into a binary tree T whose nodes hold the union of the entries in T1 and T2 and also satisfy the heap property. Your algorithm should run in O(h1 + h2) where h1 and h2 are the respective heights of T1 and T2.
  
• Exercise 9.8.
  Write a comparator for non negative integers that determines order based on the number of 1’s in each integer’s binary expansion, so that i < j if the number of 1’s in the binary representation of i is less than the number of 1’s in the binary representation of j.
  
• Exercise 9.9.
  Provide an implementation of an in-place heap-sort algorithm
  
• Exercise 9.10.
  For an ideal compression function, the capacity of the bucket array for a hash table should be a prime number. Therefore, we consider the problem of locating a prime number in a range [M,2M]. Implement a method for finding such a prime by using the sieve algorithm. In this algorithm, we allocate a 2M cell boolean array A such that the cell i is associated with the integer i. We then initialize cells to be all true and we mark off the cells that are multiple of 2,3,5,7 and so on. This process can stop after it reaches a number larger than sqrt(2M)
  
• Exercise 9.11.
  The use of null values in a map is problematic as there is then no way to differentiate whether a null value returned by the call get(k) represents the legitimate value of an entry (k, null), or designates that the key k was not found. The java.util.Map interface includes a boolean method containsKey(k) that resolves any such ambiguity. Implement such a method for the UnsortedTableMap class.

• Exercise 9.12.
  Provide an implementation of the UnsortedTableMap class that relies on the PositionalList class rather than ArrayList.

• Exercise 9.13.
  Consider the goal of adding entry (k,v) to a map only if there does not exist yet some other entry with key k. For a map M (without null values), this might be accomplished as follows:

  
  if (M.get(k) == null)
    M.put(k,v)
  

  While this accomplishes the goal, the efficiency of the method is less than ideal, as time will be spent on the failed search during the get call, and again during the put call (which always begins by trying to locate an existing entry with the given key). To avoid this inefficiency, some map implementations support a custom method ‘putIfAsbsent(k,v)’ that accomplishes this goal. Give an implementation of the ‘putIfAsbsent(k,v)’ method for the ‘UnsortedTableMap’ class

• Exercise 9.14.
  Redesign the AbstractHashMap framework to include support for a method containsKey.