CS 2401 Test #2

Date: Tuesday, March 29, 2011.

Name: ___________________________________________________________________

1-3. Consider the following method:

  public static void convert(int num, int base){
    if (0 <= num && num < base)
      convert(num / base, base);
      System.out.print(num % base);

1. Trace the execution of the following statement:
  convert(5, 2);
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:

  convert(5, 1);

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 "convert". 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, 2, 9, 20, and 11: insertion sort, merge sort, and quick sort.

6. Write a recursive code for mergesort; you can assume that the method of merging two sorted lists is already available.

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.