## CS 2401 Test #2

Date: Tuesday, July 17, 2012.

Name: ___________________________________________________________________

1-3. At every Olympics, the athletes are running 100 m faster and faster. The following method can be used to predict the corresponding time in the n-th Olympics:

```    public static double time(int n) {
if (n == 1) {return 13.0;}
else if (n > 1) {return 9.0 + 0.5 * (time(n-1) - 9.0);}
}
```
1. Trace the execution of the following statement:
```  double value = time(3);
```
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:

```  double value = time(-1);
```

3. In general, which is faster: a recursive or a non-recursive (i.e., iterative) implementation of the same method? Explain your answer.

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

4-5. Several Olympic competitions -- such as the triathlon -- consist of several consecutive stages. For example, the classical triathlon consists of swimming, cycling, and running. Let us assume that the descriptions of these stages are stored in a linked list. Write a recursive method that prints all elements of a linked list from last to first, given a reference to the head node. Trace, step-by-step, how this method will print the values of the linked list consisting of three strings: "swimming", "cycling", and "running".

6-7. Most Olympic competitions are about sorting: e.g., who is the fastest, who is second fastest, etc. Suppose that for four athletes, the following running times were recorded: 9.71, 9.89, 9.70, and 9.82 sec. Show, step-by-step, how the following three sorting methods will sort these times: insertion sort, mergesort, and quicksort. What is the worst-case and average-case computational complexity of each of these three sorting algorithms? Based on these complexities, which method would you recommend to use for the London Olympics?

8. Write Java code for mergesort; assume that the merging method is already implemented.

For extra credit: prove that mergesort is asymptotically the fastest sorting algorithm, in the sense no general sorting algorithm with a worst-case time complexity << n log(n) is possible.

9-10. As we mentioned in Problem 1-3, if we know the running record t from the previous Olympics, then the new running record can be computed as 9.0 + 0.5 * (t - 9.0). Let us assume that we know the time t = 13 from the first Olympics, and we want to find the time for the second one. Show, step by step, how, by using stacks, we can convert the above expression 9.0 + 0.5 * (13.0 - 9.0) into the postfix form and how we can compute the desired value. Write array-based methods for implementing push and pop.