EECS2030E Test 4

Version A

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 test4A.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/Test4A/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 secEtest4A Test4A.java

SOLUTION

Question 2 (12 marks total)

Consider the following method:

    /**
    * Returns true if n contains an even number of digits and false otherwise.
    * 
    * @param num
    *            an integer
    * @return true if n contains an even number of digits and false otherwise
    */
    public static boolean evenNumberOfDigits(int num) {
        if (num < 10) {
            return false;
        }
        return !evenNumberOfDigits(num / 10);
    }

A. (1 marks)

What precondition is required to ensure that the base case is correct as it is currently written?

num >= 0

B. (1 marks)

Suppose that the correct precondition from Part A is added to the method. Explain why the base case is correct.

If num is less than 10 then num must be a single digit and a number made up of a single digit has an odd number of digits. The base case correctly returns false.

C. (3 marks)

What should we assume about the recursive call evenNumberOfDigits(num / 10) if we wanted to prove that the recursive case is correct?

(num / 10) is num with its last digit removed. Assume that evenNumberOfDigits(num / 10) returns true if (num / 10) has an even number of digits and false otherwise.

D. (2 marks)

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

If evenNumberOfDigits(num / 10) returns true, then we know from the assumption that (num / 10) has an even number of digits. num has one more digit than (num / 10) so it must have an odd number of digits. The recursive case returns !evenNumberOfDigits(num / 10) which equals false which is the correct answer.

If evenNumberOfDigits(num / 10) returns false, then we know from the assumption that (num / 10) has an odd number of digits. num has one more digit than (num / 10) so it must have an even number of digits. The recursive case returns !evenNumberOfDigits(num / 10) which equals true which is the correct answer.

E. (2 marks)

Define the size of the problem solved by evenNumberOfDigits(num).

Let the size of the problem be n = the number of digits in num. n is a natural number.

Alternatively, let the size of the problem be n = num. n is a natural number.

F. (2 marks)

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

(num / 10) has 1 fewer digits than num; therefore, the recursive case solves a problem of size n - 1 < n and the method terminates.

Alternatively, the recursive case has size (num / 10) < num; therefore, the method terminates.

G. (1 marks)

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

O(n)

O(log n) if the size is defined as n = num.

submit 2030L secEtest4A answers.txt