EECS2030E Test 4

Version D

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

GETTING STARTED

  1. Start eclipse.
  2. Download this project file.
  3. 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 test4D.zip and click OK
    6. Click Finish.
  4. All of the files you need for this test should now appear in eclipse.
  5. Open a terminal. You will use this terminal to submit your work.
  6. Copy and paste the command cd workspace/Test4D/src/test4 into the terminal and press enter.

Resources

Question 1 (18 marks total)

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

submit 2030L secEtest4D Test4D.java

SOLUTION

Question 2 (12 marks total)

Consider the following method: 

 /**
  * Re-orders the elements of the argument list t so that
  * all of the negative elements of t are in the front part
  * of the list and all of the positive elements of t are
  * in the back part of the list. There is no guarantee of
  * the ordering of the positive elements or of the negative 
  * elements.
  * 
  * Zero is considered to be a positive number for the purposes
  * of this method.
  * 
  * For example, a possible solution results in the following: 
  * 
  * if t is [-1, 2]               then partition(t) makes t [-1, 2]
  * if t is [2, -1]               then partition(t) makes t [-1, 2]
  * if t is [8, -2, 1]            then partition(t) makes t [-2, 1, 8]  
  * if t is [1, -5, -9, 4]        then partition(t) makes t [-5, -9, 4, 1] 
  * if t is [-3, 7, -1, 3, -5]    then partition(t) makes t [-3, -1, -5, 7, 3]
  * 
  * @param t a list of integers
  */
 public static void partition(List<Integer> t) {
     if (t.size() < 2) {                         // base case
         return;
     }
     int first = t.get(0);
     if (first < 0) {                            // recursive case 1
         partition(t.subList(1, t.size()));
     }
     else {                                      // recursive case 2
         t.add(first);
         t.remove(0);
         partition(t.subList(1, t.size() - 1));
     }
 }
A. (1 marks)

Explain why the base case is correct when the size of t is equal to 0.

If the list is empty then there are no values to re-order; the base case does nothing which is correct.


B. (1 marks)

Explain why the base case is correct when the size of t is equal to 1.

If the list has size equal to 1 then the list is already partitioned; the base case does nothing which is correct.


C. (2 marks)

In recursive case 1, what should we assume about the recursive call partition(t.subList(1, t.size())) if we wanted to prove that the recursive case 1 is correct?

Assume that partition(t.subList(1, t.size())) re-orders all of the values of t after the first element so that they are partitioned.


D. (2 marks)

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

In base case 1, the first element of the list is negative and can remain at the front of the partitioned list. Using the assumption from Part C, the recursive invocation partitions the remaining elements of the list; therefore, the entire list is partitioned and recursive case 1 is correct.


E. (2 marks)

Define the size of the problem solved by partition(t).

Let the size by n = t.size()


F. (2 marks)

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

In recursive case 1 the size of the recursive invocation is t.subList(1, t.size()).size() == n - 1 < n; therefore, recursive case 1 terminates.

In recursive case 2 the size of the recursive invocation is t.subList(1, t.size() - 1).size() == n - 2 < n; therefore, recursive case 1 terminates.


G. (2 marks)

Recursive case 2 contains an error; what is it?

Recursive case 2 processes the sublist t.subList(1, t.size() - 1). In recursive case 2, the first element of the list is positive. Recursive case 2 removes the first element and adds it to the end of the list. We no longer need to consider the last element of the list; therefore, the end index t.size() - 1 for subList is correct. The new first element of the list is the old second element of the list, which has not been examined yet. The first index for subList should be 0 but is 1 in the given implementation.


submit 2030L secEtest4D answers.txt