Data Structures & Algorithms
CS 305 & 503

Quiz 2, 3 November 2009

1. Present an algorithm having a linear worst-case asymptotic estimate with a constant that must be at least 100. Briefly analyze how your algorithm meets the required estimate.

   ---

   The classic linear algorithm is linear search through an array:

   int find(T a[], int n, T x)
     for (i = 0; i < n - 1; i++)
       if (a[i] == x)
         return i
     return -1
   

   If we set n to be the number of elements in the array and f(n) to be the number of comparisons performed during the search, then the worst case occurs when x is not in a and find() has f(n) = O(n) with constant 1.

   To get the required estimate, find() has to perform 100 comparisons per element in a, which is easiest done using the following code:

   int find(T a[], int n, T x)
     for (i = 0; i < n - 1; i++)
       for (j = 0; j < 100; j++)
         a[i] == x
       if (a[i] == x)
         return i
     return -1
   

2. A queue can be manipulated to behave like a stack. Compare the worst-case estimates of stack push and pop operations implemented on a queue to those provided by a proper stack. Justify your comparison. You should assume that you can access only the standard queue interface (enqueue() and dequeue()) and that you cannot access the queue implementation.

   ---

   In a proper stack, the push and pop operations are both constant-estimate operations.

   A successful pop removes the newest element added to a stack; a successful deque removes the oldest element added to a queue. The newest element added to a queue is at the queue tail; to remove it from the queue, it has to be moved to the queue head, which can be done with the code

   pop()
     for i = q.size() - 1 to 0 
       q.enque(q.deque())
     return q.deque()
   

   This takes O(n) time where n is the number of elements in the queue. A push operation can be implemented as a single enque operation, which takes constant time.

3. Suppose functions g and h are worst-case estimates for the function f. If g is also a worst-case estimate for h, which of g or h is a tighter estimate for f? Justify your answer.

   ---

   Because g and h are worst-case estimates for f, they both are an upper bound for f. Similarly, g is an upper bound for h. This means that, with sufficiently large n, g(n) ≥ h(n) ≥ f(n) with suitable constants. Because h lies between g and f, it is the tighter estimate for f.

4. A case statement provides a multi-way branching statement:

   case color of
     red: // do red things.
     blue: // do blue things.
     green: // do green things.
     default: error("unrecognized color")
   

   A case statement is not one of the four algorithm components used in structural analysis to produce an asymptotic estimate. Describe a general formula that can be used to produce an asymptotic estimate for case statements during structural analysis. Justify your formula.

   ---

   Once the components of a case statement have been estimated, the case statement is

   case O(g) of
     b1: O(s1)
     // and so on
     bn: O(sn)
   

   where O(g) is the estimate for the guard and O(s_i) is the estimate for the code associated with the i-th branch. Each case-statement execution inovlves one of the branches, but which one is unknown. However, because we want a worst-case estimate, taking the largest estimate for any branch, the estimate for a case statement is

   O(case) = O(g) + max(O(s₁), …, O(s_n))

   Alternatively, the case statement

   case value of
     label1: s1
     // and so on
     labeln: sn
   

   can be implemented with the extended if statement

   v = value
   if label1 == v
     s1
   else if labeln == v
     sn
   // and so on
   

   and then generalize the asymptotic estimate for the if statement.

This page last modified on 2 November 2009.