EECS2030E Test 4

Version B

You have 80 minutes to complete this test. This is a closed book test.

GETTING STARTED

Start eclipse.
Download this project file.
Import the test project by doing the following:
1. Under the File menu choose Import...
2. Under General choose Existing Projects into Workspace and press Next
3. Click the Select archive file radio button, and click the Browse... button.
4. Navigate to your home directory (the file chooser is probably in the workspace directory).
5. Select the file test4B.zip and click OK
6. Click Finish.
All of the files you need for this test should now appear in eclipse.
Open a terminal. You will use this terminal to submit your work.
Copy and paste the command cd workspace/Test4B/src/test4 into the terminal and press enter.

Resources

Java API

Question 1 (18 marks total)

Implement the class described by this API. You do not have to include javadoc comments.

submit 2030L secEtest4B Test4B.java

SOLUTION

Question 2 (12 marks total)

Consider the following method:

  /**
   * Checks if the length of the given string is even.
   * 
   * @param s
   *            a string
   * @return true if s.length() is an even number and false otherwise
   * @pre. s is not equal to the empty string
   */
  public static boolean isEven(String s) {
      boolean result = false;
      if (s.length() == 1) {
          result = false;
      } 
      result = isEven(s.substring(2));
      return result;
  }

A. (1 marks)

What happens if you run the method when the length of s is odd?

The method returns false.

B. (1 marks)

What happens if you run the method when the length of s is even?

The method throws an IndexOutOfBoundsException because the base case is not reached.

C. (3 marks)

What should we assume about the recursive call isEven(s.substring(2)) if we wanted to prove that the recursive case is correct?

Assume isEven(s.substring(2)) returns true if s.substring(2) has an even number of characters, and false otherwise. Note that s.substring(2) has length equal to s.length() - 2.

D. (2 marks)

Using your assumption from Part C prove that the recursive case is correct.

If isEven(s.substring(2)) returns true then we know from the assumption that the string with length equal to s.length() - 2 has an even number of characters. If s.length() - 2 is even then s.length() is also even; therefore, the recursive case is correct when it returns true.

If isEven(s.substring(2)) returns false then we know from the assumption that the string with length equal to s.length() - 2 has an odd number of characters. If s.length() - 2 is odd then s.length() is also odd; therefore, the recursive case is correct when it returns false.

E. (2 marks)

Define the size of the problem solved by isEven(s).

Let the size of the problem be n = s.length()

F. (2 marks)

Using your definition from Part E prove that the method terminates.

The input to the recursive invocation is s.substring(2) which has length equal to s.length() - 2 < n; therefore, the recursive case terminates.

G. (1 marks)

What is the big-O complexity of the method? No proof is required.

O(n)

submit 2030L secEtest4B answers.txt