Sample Questions for Exam 3

Carefully define/explain the following:

L'Hopital's Rule

Refinement

Invocation (or Activation) Record

Tail Recursion

Landau Numbers

Indicate whether each of the following statements is true or false:

(1)	`_____`
(2)	`_____`	is of higher order than
(3)	`_____`	Recursion can be used to solve the Towers of Hanoi problem
(4)	`_____`	The linear search algorithm discussed in lecture has a worst case time efficiency bound that is

Carefully show that . Note: Your argument may not make use of . That is, you must work with the definition of (and limits) directly.

Choose the best answer to each of the following:

(1)	`_____`	For the bubble sort algorithm we discussed in lecture:
		None of the above
(2)	`_____`	For the merge sort algorithm we discussed in lecture:
		None of the above

Prove that if then for any constant .

What will be "drawn" by the following function if its is passed the values 0, 100, 100 when it is called originally? (Note: You should assume that the drawLine(int x1, int y1, int x2, int y2) function draws a line from the point (x1, y1) to the point (x2, y2).)

    void drawRuler(int left, int right, int level)
    {
      int mid;


      if (level < 1) return;

      mid = (left + right) / 2;
      drawLine(mid, 100, mid, 100-level*5);

      drawRuler(left, mid-1, level-1);
      drawRuler(mid+1, right, level-1);
    }

Write a recursive function that is passed two values, and , and returns .
What is the asymptotic bound on the worst case time efficiency of the function in the previous question? (Note: Your answer must be given in terms of .)

Carefully derive the asymptotic bound on the worst case time efficiency of the following function in terms of n (the size of the array). Explain each step of your derivation. (Note: Your answer must be given in terms of .)

  double  *moments(double x[], int n, int k) {

    double  xbar, sum;
    double  *m, *total;
    int     i, j;

    // Initialization
    //
    m     = new double[k+1];
    total = new double[k+1];

    for (i=0; i<=k; i++) {
    
      m[i] = 0;
      total[i] = 0;
    }


    if (k >= 2) {

      // Calculate the mean
      //
      sum = 0;
      for (i=0; i<n; i++) {

        sum += x[i];
      }
      xbar = sum/(double)n;



      // Calculate moments 2 through k
      //
      for (j=2; j<=k; j++) {
        for (i=0; i<n; i++) {

          total[j] += pow((x[i] - xbar), j);
        }
        m[j] = total[j] / (double)n;
      }
    }
    delete[] total;

    return m;
  }

The Fibonacci Numbers are commonly defined as follows: , , and for . Given this definition, complete the following function. Your solution must use recursion.
```
  /**
   * Calculates the nth Fibonacci Number
   *
   * @param n  The desired Fibonacci Number (must be positive)
   */
  int fibonacci(int n)
  {



  }
  
```
The recursive algorithm:
```
double power(double x, unsigned int n)
{
    if (n == 0) return 1.0;
    else        return x*power(x, n-1);
}
```
is fairly inefficient. For example, observe that the computation of requires 8 multiplications. However, if we observe that then we can make this algorithm more efficient.

Use this observation to improve this algorithm. Your answer must be recursive. Hint: A special case is needed for odd exponents.
What is the asymptotic bound on the worst case time efficiency of your solution to the previous question? (Note: Your answer must be given in terms of .)
In the movie Pay It Forward the star does a good deed for 3 different people. Each, in turn, is supposed to do a good deed for 3 people, etc... Assuming that there is no duplication, and that each person accomplishes their good deeds in a single day, and that I started a similar the process at JMU today, how long would it took for all of the approximately 20,000 people in the JMU community to be the recipient of a good deed? (Show all of your work.)

Suppose that the function sort is implemented as follows:

  void sort(int a[], int length)
  {
    int i, j, k, h, tmp;
    int cols[3] = {7, 3, 1};


    for (k=0; k<3; k++)
    {
      h = cols[k];

      for (i=h; i<length; i++)
      {
        tmp = a[i];
        j = i;

        while ( (j>=h) && (a[j-h]>tmp) )
        {
          a[j] = a[j-h];
	  j = j - h;
        }
        a[j]=tmp;
      }

      cout << endl << "Iteration " << k << ":   ";
      for (i=0; i<length; i++)
      {
        cout << a[i] << "   ";
      }
      cout << endl;
    }
  }

What will be printed when the following main function is executed?

  int main(void)
  {
    int a[6] = {8,4,7,3,9,3};
    int i, n;

    n = 6;
    sort(a, n);

    return 1;
  }

Sort the following array using the "insertion sort" algorithm. Show all of your work.
[4, 4, 1, 0, 4, 4, 1, 0, 1, 1]
Would you recommend using an "insertion sort" algorithm or a "counting sort" algorithm to sort the array in the previous example? Why?
Re-write the selection sort algorithm we discussed in lecture so that it uses a linked list rather than an array.
The cocktail shaker sort is a variant of bubble sort. In this sort, elements are swapped up the array first, placing the largest value at the top end, then elements are swapped down the array, placing the smallest value in the initial position, then elements are swapped up the array again, and so forth. Implement the cocktail shaker sort algorithm in C++.