Data Structures & Algorithms

Exam 1

Sample 1, 75 Minutes

Solutions

1. (a) The code is given below.

   
   public void rightShift(int k)
   {// Shift elements right by k.
      // make sure k is nonnegative
      if (k < 0)
         throw new IllegalArgumentException("Shift amount must be >= 0");
   
      // make sure we have enough space
      if (size + k > element.length)
      {// get larger array
         Object [] newArray = new Object [size + k];
         for (int i = 0; i < size; i++)
            newArray[i] = element[i];
         element = newArray;
      }
   
      // shift elements from right to left
      for (int i = size - 1; i >= 0; i--)
         element[i+k] = element[i];
   
      // zero fill at left end
      for (int i = 0; i < k; i++)
         element[i] = null;
   
      size += k;  // new size
   }
   
   

   (b)

   When an exception is thrown the complexity is Theta(1). Otherwise, it takes O(size + k) time to increase the array size (if necessary). The second for loop takes O(size)), and the third loop takes O(k) time. Therefore, the complexity is O(size+k).

   
   
   
2. (a) The code is given below.

   
   public boolean isSorted()
   {// Return true if the elements are in
    // nondecreasing order; return false otherwise.
      if (firstNode == null)
          return true;  // empty
   
      // check nonempty chain
      ChainNode currentNode = firstNode,
                nextNode = firstNode.next;
      while (nextNode != null)
      {
         if (((Comparable) currentNode.element).compareTo(nextNode.element) > 0)
            return false;
         currentNode = nextNode;
         nextNode = currentNode.next;
      }
      return true;
   }
   
   

   (b)

   The while iterates at most size-1 times and each iteration takes Theta(1) time. The remaining lines take Theta(1) time. Therefore, the overall complexity is O(size).

   
   
3. (a) A sample 4 x 4 N-matrix is given below.

                       1 0 0 2
                       3 4 0 5
                       6 0 7 8
                       9 0 0 1
   

   The compact representation is [1,3,6,9,2,5,8,1,4,7].
   (b) The code is given below.

   
   public void set(int i, int j, Object newValue)
   {// Store newValue as N(i,j).
      if ( i < 1 || j < 1 || i > n || j > n)
          throw new IllegalArgumentException("index out of range");
   
      if (j == 1)
         element[i-1] = newValue;          // first column
      else 
         if (j == n)
            element[n+i-1] = newValue;     // last column
         else
            if (i == j)
               element[2*n+i-2] = newValue;       
                            // rest of diagonal
            else
               if (!newValue.equals(zero))
                  throw new IllegalArgumentException("value must be zero");
   }