Problem Set 4. Posted 2/9

1. Consider a boolean n by n 2-dimensional array and suppose that this array has lots of false values and very few true values. A much more compact representation (that is, a representation that saves memory) of this array would be one in which we only keep track of the positions of the true values. Specifically, given a boolean n by n 2-dimensional array A, we can represent it using an integer 2-dimensional array B. B has the same number of rows as A and in each row i, 0 <= i < n of B, we would store the column indices of all the true values in row i of A. For example, if A were a 3 by 3 boolean array with F, F, and T in row 0, then row 0 of B would contain just one element, 2. If row 1 of A were T, F, and T then row 1 of B would contain two elements, 0 and 2.

   Write a function called sparsify that takes a boolean n by n 2-dimensional array A and returns the equivalent, sparse representation B. Use the following function header for your function:

   public static int[][] sparsify(boolean[][] A)

2. Implement a Queue ADT using an array representation. A Queue ADT represents a collection of items under the following operations:
   • Insert: add the given item to the collection.
   • Delete: delete the oldest item from the queue and return it.
   • IsEmpty: returns true if the Queue is empty and false otherwise.
   Assuming that the items in the Queue are going to be integers, these operations would correspond to the following function headers in a Queue class:
   • public static void enqueue(int item)
   • public static int dequeue()
     
   • public static boolean isEmpty()
     
   In the above list, enqueue corresponds to insert and dequeue corresponds to delete.

   Implement the Queue class using an array to store the items in the queue. Specifically, use a 1-dimensional integer array called data to store the items. Also, use two integer variables front and back to keep track of the front and the back of the queue. In particular, the oldest item (the one that was inserted earliest) in the queue would be in the slot whose index is front and the youngest item (the one that was inserted most recently) in the queue would be in a slot whose index is back. In general, if we read items in data starting from the index front and moving towards the index back, we would encounter items in the order in which they were inserted into the queue.

   If you are not careful, it is quite possible to believe that array data is full, even when it is not. For example, suppose data is an array of size 3. Consider the sequence of operations: insert 5, insert 7, delete, insert 2, delete. At this time, the Queue has only one item and this is occupying the last slot (slot number 2) of the array. What happens if the next operation is an insert operation? Since there is no slot after the slot that back is pointing to, should we just claim that the Queue is full? No, we should just wrap around and insert the new item in slot 0 and continue in this manner.

   Make sure that you do resize the array data (by doubling it) when the Queue is really full and an insert operation is performed.

3. Here are some questions about the efficiency of the two implementations described in the previous problems:
   1. Suppose that we have called the function sparsify on a boolean n by n 2-dimensional array A and constructed an equivalent, but much more compact representation B. Describe (in 1-2 sentences) how you would implement the operation equivalent to A[i][j] = false on B. What is the worst case running time of this operation (as a function of n)? Please justify your anawer.
   2. What is the worst case running time of the enqueue operation on a Queue object with n items in it? Explain your answer.
   3. Suppose that we pay 1 dollar when we enqueue into a Queue that is not full. Further suppose that we pay k dollars when we enqueue into full Queue with k elements in it. Let us suppose that our policy is to start with a Queue of size one and double the size of the Queue each time it becomes full. What is the total number of dollars we pay for 20 enqueue operations?