EECS2030 Test 5D

Programming question

Implement the Test5D class.

The API can be found here.
The Java library API can be found here.
You have to put your Test5D class in the test5 package.
You have to use recursion.
You must not use any kind of for statement or while statement.

Other questions

Consider the following method:

/**
 * Returns true if the character c appears in s, and false otherwise.
 *
 * @param s a string
 * @param c a character to search for in s
 * @return true if the character c appears in s, and false otherwise.
 */
public static boolean contains(String s, char c) {
  int result = false;
  if (s.isEmpty()) {
    result = false;
  }
  else if (s.charAt(0) == c) {
    result = true;
  }
  else {
    String t = s.substring(1, s.length());
    result = contains(t , c);
  }
  return result;
}

Question 1

Prove the above method correct.

Question 2

Prove that the above method terminates.

Question 3

Give the recurrence relation of the above method.

Question 4

Let f : ℕ → ℕ be defined by f(n) = n³ + 11n. Then f ∈ O().

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.
Let M = ??? Let m = ??? Then, ...

Question 6

Provide the Javadoc comments needed to reproduce the API for the two methods in the programming question. You may omit the part of the comments that describe the examples and preconditions (i.e., document the parameters, the return value (if any), and the first sentence of the method description).