EECS2030 Test 5F

Tuesday Nov 29 16:00-17:20
Lab 02
Version E


Instructions

There is one programming question and five other questions.

Instructions for submitting your programming question solution are given in the Programming question section. You may submit as many times as you want; your most recent submission will be the one recorded.

Instructions for submitting your answers to the short answer questions are given in the Short Answer Questions section. You may submit as many times as you want; your most recent submission will be the one recorded.

Programming question


Implement the Test5F class and provide the Javadoc comments needed to reproduce the API for the two required methods. You may omit the part of the comments that describe the examples (i.e., document the parameters, the return value (if any), and the method description excluding the examples).

Submit your program using the following command in a terminal (make sure you are in the directory containing your file Test5F.java):

submit 2030 test5F Test5F.java


Other questions

Consider the following method:
  /**
   * Returns the string made up of the characters in s starting
   * from index idx and going to the end of s. For
   * example,
   * 
   * endOf("abcdef", 0) returns "abcdef"
   * endOf("abcdef", 1) returns "bcdef"
   * endOf("abcdef", 2) returns "cdef"
   * endOf("abcdef", 3) returns "def"
   * 
   * An empty string is returned if idx is greater than or equal to
   * the length of s.
   * 
   * @param s
   *          a string
   * @param idx
   *          the starting index in s
   * @pre. idx >= 0
   * @return the string made up of the characters in s starting from index idx
   *         and going to the end of s
   */
  public static String endOf(String s, int idx) {
    String result = "";
    if (idx >= s.length()) {
      result = "";
    }
    else {
      result = s.charAt(idx) + endOf(s, idx + 1);
    }
    return result;
  }
Question 1 (3 marks)

Prove that the above method is correct.



Question 2 (3 marks)

Prove that the above method terminates.



Question 3 (2 marks)

Let f : ℕ → ℕ be defined by f(n) = 5n4 + 3n + 2. Prove that f ∈ O(n4). 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.

You may write n4 as n^4 in your answer.



Question 4 (1 mark)

In our discussion of model-view-controller, we said that the controller responds to events. When are events generated in a graphical user interface application? (a one sentence answer should be sufficient)



Question 5 (1 mark)

In the linked list implementation discussed in the lectures, why is the Node class a private inner class of LinkedList? (a one or two sentence answer should be sufficient)