Data Structures & Algorithms

Exam 1

Sample 2, 75 Minutes

Solutions

1. (a) The code is given below.

   
   public void compress()
   {// Eliminate element[i], i = 1, 3, 5, ... and pack.
   
      // eliminate and pack left to right
      for (int i = 2; i < size; i += 2)
         element[i / 2] = element[i];
   
      // should set element[newSize : size-1] to null to
      // enable garbage collection, not required for test
   
      size = (size + 1) / 2;  // new size
   }
   
   

   (b)

   The for loop iterates O(size) times, and each iteration takes O(1) time. The remainder of the code takes O(1) time. Therefore, the overall complexity is O(size).

   
   
   
2. (a) The code is given below.

   ---

   public static void threeWaySplit(Chain a, Chain b, Chain c, Chain d)
   {// Split a into three chains b, c, and d.
    // When done, a is unchanged.
      // empty out b, c, and d
      b.makeEmpty();
      c.makeEmpty();
      d.makeEmpty();
   
      // assign elements to b, c, and d
      Iterator ia = a.iterator();  // iterator for a
      while (ia.hasNext())
      {
         // first give b an element
         b.append(ia.next());
         if (!ia.hasNext())
            break;
         // now give c an element
         c.append(ia.next());
         if (!ia.hasNext())
            break;
         // now give d an element
         d.append(ia.next());
      }
   }
   

   ---

   
   

   (b)

   The time needed to make the chains b, c, and d empty is O(1). The while loop iterates O(size of a) times. So, the complexity is O(size of a).

   
   
3. (a) A sample 5 x 5 S-matrix is given below.

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

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

   
   public Object get(int i, int j)
   {// return S(i,j)
      if ( i < 1 || j < 1 || i > n || j > n)
          throw new IllegalArgumentException("index out of range");
   
      if (i == 1)
         // first row
         return element[j - 1];
   
      if (i == n / 2 + 1)
         // middle row
         return element[n + j - 1];
   
      if (i == n )
         // bottom row
         return element[2 * n + j - 1];
   
      if (i <= n / 2 && j == 1)
         // first column of S
         return element[3 * n + i - 2];
   
      if (i > n / 2 + 1 && j == n)
         // last column of S
         return element[3 * n + i - 3];
      else 
         // not in S
         return zero;
   }