CS 503, Advanced Programming I

Quiz 1, 30 January 2007

1. A friend of yours doesn't beleive that the function f(n) = n² can have an upper bound, because for any value x, you can always find a value of n such that f(n) > x. Although right about x, your friend is wrong about the upper bound. Explain why.

   ---

   Your friend is comparing two different values of n rather than comparing the same value. That is, g is an upper bound for f if, for the same value of n g(n) ≥ f(n).

   ---

2. Draw pictures of the given variables at points 1, 2, and 3 in the following code:

   int i = 2;
   int * ip = &i;
   /* point 1 */
   i = 3;
   /* point 2 */
   *ip = 8;
   /* point 3 */
   

   ---

   

   ---

3. Provide a worst-case estimate of the following procedure:

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

   Be sure to show all your steps and state your assumptions.

   ---

   Starting with individual statements:

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

   The if statement's next:

   int find(int a[], int n, int x)
   
     for (i = 0; i < n; i++)
       O(1) + O(min(1, 1) = O(1) + O(1) = O(1)
     O(1)
   

   The array access takes constant time, as does the comparison. The for loop is equivalent to a while loop with some overhead.

   int find(int a[], int n, int x)
   
     i = 0
     while i < n
       O(1)
       i++
     O(1)
   

   Prefix increment takes constant time, as does the assignment to i.

   int find(int a[], int n, int x)
   
     O(i)
     while i < n
       O(1)
       O(1)
     O(1)
   

   The sequence of two constant-time statements is again a constant time statement.

   int find(int a[], int n, int x)
   
     O(1)
     while i < n
       O(1) + O(1) = O(max(1, 1)) = O(1)
     O(1)
   

   The number of interations is bounded by n and the comparison takes constant time.

   int find(int a[], int n, int x)
   
     O(1)
     O(n)*(O(1) + O(1) = O(n)*O(1) = O(n*1) = O(n)
     O(1)
   

   Combining the remaining statement sequence gives the final answer

   int find(int a[], int n, int x)
   
     O(1) + O(n) + O(1) = O(1) + O(max(n, 1)) = O(1) + O(n) = O(n)
   

   ---

4. Show the regular language generated by the a ? ( a ? a ) regular expression.

   ---

   All the strings start with a. The first option may contribute a futher a followed by an optional a or not.

   a
   a a ? a
   

   The final option may contribute an a or not.

   a
   a a
   a a a
   

   ---

This page last modified on 7 February 2006.