CS 2401 Test #2

Date: Thursday, October 27, 2011.

Name: ___________________________________________________________________

On October 27, 1904, the first line of the New York City subway was officially launched. Very soon, it became -- and stays -- the largest subway system in the world.

1-3. To determine how much time remains until the next inspection of a train, the following method is used:

  public static int howMuch(int produced, int current){
    if (current == produced) {return 5;}
    else{return howMuch(produced, current - 1) - 1;}

1. Trace the execution of the following statement:
  int yearsRemaining = howMuch(2009, 2011);
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 yearsRemaining = howMuch(2009, 2008);

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 "howMuch" in terms of its inputs. Show how this value can be computed without recursion.

4-5. A train is formed by putting together several train cars. Different trains have different number of cars -- more in rush hours, when there are more passengers, and fewer late at night. Because of this, it is reasonable to use a linked list of car numbers to describe each train. To be able to estimate how many cars are in each train, write a recursive method that computes the number of elements in a linked list, given a reference to the head node. Trace, step-by-step, how this method will work on a train consisting of cars with the numbers 1234, 1235, and 1997.

6. To make it easier for passengers to find the station, the list of subway stations lists them in alphabetic order. Let us assume that we have stations named A, D, B, X, and Z, which are given in an array of chars. ow, step-by-step, how the following three sorting methods will sort these names: insertion sort, merge sort, and quick sort.

7. Write a method in Java code for insertion 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 sorting station names?

9. Subway trains run on electric energy. According to elementary physics, the amount of energy needed to accelerate the train of mass m to velocity v is equal to m * v * v / 2. 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 m = 200 ton and v = 100 km/h.

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