Exam 1

Sample 1, 50 Minutes

Solutions

(a) The code is given below. The relevant files are jlist.*.


template<class T>
LinearList<T>& LinearList<T>::RightShift(int k)
{// Shift elements right by k.
 // Zero fill at left end.
 // Throw NoMem if space inadequate.
   // make sure k is nonnegative
   if (k < 0) throw BadInput();

   // make sure we have enough space
   if (length + k > MaxSize) throw NoMem();

   // shift elements from right to left
   for (int i = length - 1; i >= 0; i--)
      element[i+k] = element[i];

   // zero fill at left end
   for (int i = 0; i < k; i++)
      element[i] = 0;

   length += k;  // new length

   return *this;
}

(b): When an exception is thrown the complexity is Theta(1). Otherwise, the first for loop takes Theta(length) time, and the second loop takes Theta(k) time. Therefore, when an exception is not thrown, the complexity is Theta(length+k). Combining the complexities for the cases when an exception is and is not thrown, the complexity becomes O(length+k).

(a) The code is given below. The relevant files are ichain.*.


template<class T>
bool Chain<T>::IsSorted() const
{// Return true if the elements are in
 // nondecreasing order; return false otherwise.
   if (!first) return true;  // empty

   // check nonempty chain
   ChainNode<T> *current = first,        // current node
                *next = first->link;     // next node
   while (next) {
      if (current->data > next->data)
         return false;
      current = next;
      next = current->link;
      }
   return true;
}

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

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

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


template<class T>
NMatrix<T>& NMatrix<T>::
     Store(const T& x, int i, int j)
{// Store x as N(i,j).
   if ( i < 1 || j < 1 || i > n || j > n)
       throw OutOfBounds();
   if (j == 1) t[i-1] = x;          // first column
   else if (j == n) t[n+i-1] = x;   // last column
        else if (i == j) t[2*n+i-2] = x;
                         // rest of diagonal
             else if (x != 0) throw MustBeZero();
   return *this;
}

BACK