Exam 1

Sample 2, 50 Minutes

Solutions

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


template<class T>
LinearList<T>& LinearList<T>::InsertZero(int i, int k)
{// Insert k zeroes after element i.
 // Throw BadInput exception if no i'th element or k < 0.
 // Throw NoMem exception if inadequate space.
   if (k < 0 || i < 0 || i > length)
       throw BadInput();
   if (length + k > MaxSize) throw NoMem();

   // move k positions up
   for (int j = length-1; j >= i; j--)
      element[j+k] = element[j];

   // fill with zeroes
   for (int j = i; j < i + k; j++)
      element[j] = 0;

   length += k;
   return *this;
}

(b): When an exception is thrown the complexity is Theta(1). Otherwise, the first for loop takes O(length) time, and the second loop takes Theta(k) time. Therefore, when an exception is not thrown, the complexity is O(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 kchain.*.


template<class T>
bool Chain<T>::Bitonic() const
{// Return the true iff the chain is bitonic.
   // empty chain is bitonic
   if (!first) return true;
   
   // find first adjacent pair of unequal elements
   T e = first->data;
   ChainNode<T> *c = first->link;  // cursor
   while (c && e == c->data)
      c = c->link;

   // did we find an element different from e?
   if (!c) // all elements are equal
      return true;

   // elements e and c->data are different
   if (e < c->data) {// first part is nondecreasing
      // bypass nondecreasing part
      T last = c->data;
      c = c->link;
      while (c && last <= c->data) {
         last = c->data;
         c = c->link;
         }
      if (!c) // all are nondecreasing
         return true;
      // elements remain, rest must be nonincreasing
      last = c->data;
      c = c->link;
      while (c && last >= c->data) {
         last = c->data;
         c = c->link;
         }
      // list is bitonic iff c = 0
      if (c) return false;
      else return true;
      }
   else {// first part is nonincreasing
      // bypass nonincreasing part
      T last = c->data;
      c = c->link;
      while (c && last >= c->data) {
         last = c->data;
         c = c->link;
         }
      if (!c) // all are nonincreasing
         return true;
      // elements remain, rest must be nondecreasing
      last = c->data;
      c = c->link;
      while (c && last <= c->data) {
         last = c->data;
         c = c->link;
         }
      // list is bitonic iff c = 0
      if (c) return false;
      else return true;
      }
}

(b): The while loops iterate at most length 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 Z-matrix is given below.

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


template<class T>
ZMatrix<T>& ZMatrix<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 (i == 1) t[j-1] = x;          // first row
   else if (i == n) t[n+j-1] = x;   // last row
        else if (i+j == n+1) t[2*n+i-2] = x;
                   // rest of cross diagonal
             else if (x != 0) throw MustBeZero();
   return *this;
}

BACK