EECS1030Z Test 5

Wednesday April 1, 2015, 14:30-15:45
Lab 02
Version C

package test5;

import java.util.List;

public class Test5C {
  private Test5C() {
  }
  
  /**
   * Returns the string that counts down in steps of one starting
   * from n and ending at 1 followed by "Liftoff!". For example,
   * 
   * Test5C.countdown(5) returns the string
   * "5, 4, 3, 2, 1, Liftoff!"
   * 
   * @param n the number to count down from
   * @pre. n > 0
   * @return the countdown string described above 
   */
  public static String countdown(int n) {
    String s = "";
    if (n == 0) {
      s = "Liftoff!";
    }
    else {
      s = n + ", " + Test5C.countdown(n - 1);
    }
    return s;
  }
  
  
  /**
   * Moves the maximum element in a list to the end of the list.
   * For example, if t is the list:
   * 
   * [100, 2, 1, 3]
   * then Test5C.maxToEnd(t) rearranges the elements in
   * t to [2, 1, 3, 100]
   * 
   * The ordering of the elements before the last element is unspecified,
   * but no element is removed from or added to t
   * 
   * @param t the list to move the maximum element to the end of
   * @pre. t.size() >= 0
   */
  public static void maxToEnd(List<Integer> t) {
    if (t.size() > 1) {
      int first = t.get(0);
      int second = t.get(1);
      if (first > second) {
        t.set(0, second);
        t.set(1, first);
      }
      Test5C.maxToEnd(t.subList(1, t.size()));
    }
  } 
}

Other questions

Consider the following method: 
/**
 * Returns the value of the sum:
 *
 * m + (m + 1) + (m + 2) + ... + n
 *
 * @param m an integer
 * @param n an integer
 * @pre. m <= n
 * @return the value of the sum of the numbers from m to n
 */
public static int sum(int m, int n) {
  int val = 0;
  if (m == n) {
    val = n;
  }
  else {
    val = m + sum(m + 1, n);
  }
  return val;
}
Question 1

Prove the above method correct.

First, we consider the first base case: m == n. This should compute the
sum n, which it does. Therefore, the base case is correct.

Finally, we consider the recursive case: m != n and m < n (from the
precondition and the fact that we are not in the base case). We assume
that sum(m + 1, n) correct computes the sum:

  (m + 1) + (m + 2) + ... + n.

The recursive case computes the sum:

  m + sum(m + 1, n) = m + (m + 1) + (m + 2) + ... + n

which is exactly the value promised by the postcondition.


Question 2

Prove that the above method terminates.

We define the size of the invocation sum(m, n) to be equal to equal to
(n - m + 1), which is the number of values to sum.

Next, we consider the recursive case: sum(m + 1, n). The size of the
invocation is

  n - (m + 1) + 1 = n - m

which is less than (n - m + 1)


Question 3

Give the recurrence relation of the above method.

T(n) = T(n - 1) + constant

The time it takes to solve a problem of size n is equal to the
the time it takes to solve a problem of size (n - 1) plus a constant
amount of work.


Question 4

Let f : ℕ → ℕ be defined by f(n) = 2n2 + 10n - 1. Then f ∈ O(n2)



Question 5

Prove your answer to Question 4. You must state reasonable values of M and m (or F and M if you are using the notation from the notes) and then prove that the appropriate inequality is true.