CS 2401 Test #2

Date: Wednesday, October 26, 2011.

Name: ___________________________________________________________________

On October 26, 1959, the first photos of the Far Side of the Moon were taken by the Luna spaceship.

1-3. The following method was used in computing the spaceship trajectory (of course, it was not programmed in Java since Java did not exist in 1959 :-)

  public static double luna(double x, int n) {
    if (n == 0) {return 1;}
    else if (n > 0) {return x * luna(x, n-1);}
    else {return luna(x, n+1) / x;}

1. Trace the execution of the following statement:
  double value = luna(3.0, 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:

  double value = luna(0.0, -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 "luna" in terms of x and n. Show how this value can be computed without recursion.

4-5. Before the launch of a spaceship, it is necessary to perform a sequence of tests. Let us assume that the descriptions of these tests are stored in a linked list. Write a recursive method that prints all elements of a linked list from first to last, 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: "Test main engine", "Test second stage", and "Test photo camera".

6. Communication with a spaceship near the Moon is difficult -- even at the speed of light, the signal takes more than one second to go from the Earth to the Moon. To avoid critical delays, it is important to prioritize communications: some messages (e.g., that some equipment is not working well) are of highest importance, others are of lower importance. Suppose that the system receives five messages ready for transmission, with priorities 0, 5, 3, 1, and 2 (5 is the highest, 0 is the lowest) listed in an array. Show, step-by-step, how the following three sorting methods will sort these messages: bubble sort, merge sort, and quick sort.

7. Write a method in Java code for bubble sort.

8. 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 spaceship control?

9. Suppose that we consider a linear fragment of the spaceship trajectory. At moment t1, the spaceship was at location x1; at moment t2, it moved to the location x2. We can then estimate the speed of the spaceship as (x2 - x1) / (t2 - t1). Convert this expression into a postfix form. Show, step-by-step, how, by using stacks, we can compute the value of the resulting postfix expression when t1 = 100 sec, t2 = 101 sec, x1 = 3,000 km, and x2 = 3,012 km.

10. Write two methods for implementing push in both possible representations of stacks: as arrays and as linked lists.