**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);

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:

- convert the expression (3 - 3 - 0) * (20 - 1 - 1) into a postfix form, and
- compute the value of the resulting postfix expression.

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.