EECS2030E Test 4

Version C

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 test4C.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/Test4C/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 secEtest4C Test4C.java

SOLUTION

Question 2 (12 marks total)

Consider the following method:

/**
  * Returns true if x is a prime number and false otherwise.
  * An integer number x is prime if the only divisors of
  * x are 1 and x.
  * 
  * @param x
  *          an integer value greater than 2
  * @param y
  *          a number used to divide x by
  * @return true if x is prime and false otherwise
  */
 private static boolean isPrime(int x, int y) {
     if (y > 0.5 * x) {            // base case 1
         return true;
     }
     if (x % y == 0) {             // base case 2
         return false;
     }
     return isPrime(x, y + 1);     // recursive case
 }

A. (1 marks)

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

x > y && y > 1

B. (1 marks)

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

If (x % y == 0) is true, then y is a divisor of x that is not equal to x nor 1; therefore, x is not a prime number. Base case 2 returns false, which is correct.

C. (3 marks)

What should we assume about the recursive call isPrime(x, y + 1) if we wanted to prove that the recursive case is correct?

Assume isPrime(x, y + 1) returns true if x is prime and false otherwise.

D. (2 marks)

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

This question is poorly written; all students will receive 2 marks regardless of their answer.

The recursive case runs when the integers 2 through y are not divisors of x and y is less than 0.5 * x. We still need to check if any of the values y + 1 through x / 2 are divisors of x, which is accomplished using the assumption from Part C.

E. (2 marks)

Define the size of the problem solved by isPrime(x, y).

Let the size be n = 0.5x - y where 0.5x is the integer equal to 0.5 * x rounded up to the nearest integer. n is a natural number (assuming that the precondition from A is included).

F. (2 marks)

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

The size of the recursive invocation is n = 0.5x - (y + 1) = 0.5x - y - 1 < n; therefore, the recursive case terminates.

G. (1 marks)

Base case 1 is technically correct but there is a different base case that could be used instead to dramatically reduce the number of recursive calls needed to determine if x is prime or not. What is the (much) more efficient base case?

The largest divisor of x that is not equal to x is the integer equal to the square root of x (assuming such an integer exists). Therefore, the condition for base case 1 could be:

if (y > Math.sqrt(x))

submit 2030L secEtest4C answers.txt