CS 2401 Test #2

Date: Wednesday, March 30, 2011.

Name: ___________________________________________________________________

1-3. Consider the following method:

  public static int df(int a){
    if (a == 1 || a == 2) {
      return 1;
    return a * df(a-2);

1. Trace the execution of the following statement:
  int x = df(5);
Reminder: Your trace should show successive calls to the method. For each call, the trace should include the values of the parameters and the value returned to the caller.

2. Describe what would happen if the following statement was executed:

  int x = df(0);

3. In general, which is faster: recursive or a non-recursive program? Explain your answer.

For extra credit: Write down the exact function computed by method "df" in terms of a. Show how this value can be computed without recursion.

4. Explain the general algorithm for solving the Hanoi tower problem. Draw, step-by-step, the solution to the Hanoi Tower problem for the case when we have three disks.

5. Show, step-by-step, how the following three sorting methods will sort a list consisting of the numbers 3, 30, 2, 0, and 11: insertion sort, merge sort, and quick sort.

6. Write a code for insertion sort.

7. What is the computational complexity of each of these sorting algorithms?

For extra credit: Prove that we cannot sort a list faster than in n * log(n) steps.

8-9. Show, step-by-step, how, by using stacks, we can:

10. Write a general method that uses a stack to compute the value of a postfix expression given as a string. Assume that there are no blanks, and that all numbers have only one digit.