EECS2030 Test 5C

Monday Dec 05 14:00-15:20
Lab 01
Version C

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

Programming question

Implement the Test5C 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 Test5C.java):

submit 2030 test5C Test5C.java

 
package eecs2030.test5;

import java.util.List;

public class Test5C {
    private Test5C() {
        // prevent instantiation
    }
    
    /**
     * Returns the string equal to the string formed by
     * removing all of the 'a' and 'A' characters from the
     * argument string s.
     * 
     * <p>
     * For example:
     * </p>
     * 
     * <pre>
     * Test5C.removeA("") returns the empty string
     * Test5C.removeA("a") returns the empty string
     * Test5C.removeA("B") returns the string "B"
     * Test5C.removeA("ABA") returns the string "B"
     * Test5C.removeA("BananA") returns the string "Bnn"
     * Test5C.removeA("aaaaAAAaaA") returns the empty string.
     * </pre>
     * 
     * 
     * @param s a non-null string
     * @return the string equal to removing all of the lower
     * and uppercase a's from the argument string s
     */
    public static String removeA(String s) {
        if (s.isEmpty()) {
            return s;
        }
        char first = s.charAt(0);
        if (first == 'a' || first == 'A') {
            return Test5C.removeA(s.substring(1));
        }
        return first + Test5C.removeA(s.substring(1));
    }
    
    /**
     * Computes the sum of the elements in the argument list
     * t starting from the first element and skipping every
     * second element. The sum of an empty list is zero.
     * 
     * <p>
     * For example:
     * </p>
     * 
     * <pre>
     * if t is []                 then Test5C.sumSkip(t) returns 0
     * if t is [1]                then Test5C.sumSkip(t) returns 1 
     * if t is [-1, 2]            then Test5C.sumSkip(t) returns -1 
     * if t is [1, 2, 8]          then Test5C.sumSkip(t) returns 9 
     * if t is [1, 0, -9, 4]      then Test5C.sumSkip(t) returns -8 
     * if t is [1, 2, 12, -3, 15] then Test5C.sumSkip(t) returns 28 
     * </pre>
     * 
     * @param t a non-null list of integers
     * @return the sum of all of the elements of t having an
     * even index
     */
    public static int sumSkip(List<Integer> t) {
        if (t.isEmpty()) {
            return 0;
        }
        else if (t.size() < 3) {
            return t.get(0);
        }
        int sum = t.get(0) + sumSkip(t.subList(2, t.size()));
        return sum;
    }
  
}

Other questions

Consider the following method: 
    /**
     * Removes all duplicated strings from a non-null and sorted list of strings
     * maintaining the sorted order of the strings. If the list contains unique
     * strings then the list remains unchanged. For example, if t is the list
     * ["a", "b", "c", "d"] then unique(t) would do nothing. If t is the list
     * ["w", "w", "w", "x", "y", "y", "z"] then unique(t) would modify t so that
     * it became the list ["w", "x", "y", "z"].
     * 
     * @param t
     *            a non-null and sorted list of strings that the method modifies
     *            so that it contains no duplicated strings (and the list remains in
     *            sorted order).
     */
    public static void unique(List t) {
        if (t.size() < 2) {
            return;
        }
        String first = t.get(0);
        String second = t.get(1);
        if (first.equals(second)) {
            t.remove(0);
            Test5C.unique(t);
        }
        Test5C.unique(t.subList(1, t.size()));
    }
Question 1 (3 marks)

Prove that the above method is correct.

(1 / 1) There are no duplicate elements in a list of size less than 2. The method does nothing in this case; therefore, the base case is correct.

(2 / 2) Assume unique(t) modifies t so that it contains no duplicates and maintains its sorted order. There are two cases to consider. (1) If the first two elements are equal then the method removes the first duplicated element. The method then recursively modifies t so that it contains no duplicates and maintains its sorted order. (2) If the first two elements are not equal, then the first element is unique because the list is in sorted order. The method leaves the first element intact and then recursively modifies the remainder of the list so that it contains no duplicates and maintains its sorted order.



Question 2 (3 marks)

Prove that the above method terminates.

(1 / 1) Let the size of the problem unique(t) be n the size of the list t (which is a non-negative integer value).

(2 / 2) There are two different recursive invocations. (1) The first invocation removes one element from the list and then recursively invokes unique on the shortened list. The size of this problem is (n - 1) which is less than n. (2) The second invocation Test5C.unique(t.subList(1, t.size())) operates on the sublist of size (n - 1) which is less than n.



Question 3 (1 mark)

State the recurrence relation of the above method.

Unless you explicitly state that the list is a linked list, the recurrence relation is

T(n) = T(n - 1) + n

because removing an element from the front of a list is an element of O(n)



Question 4 (2 marks)

Let f : ℕ → ℕ be defined by f(n) = 3n4 + 5n2 + 1. 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 and n2 as n^2 in your answer.

3n^4 + 5n^2 + 1 < 3n^4 + 5n^4 + 1n^4 for all n > 1
= 9n^4

Therefore, for M = 9 and m = 1 we have

| 3n^4 + 5n^2 + 1 | < | 9n^4 | for n > 1


Question 5 (1 mark)

Consider the linked list data structure described in the lecture slides. Explain (using 1-3 sentences) why it is inefficient to insert an element at the end of a linked list.

It is inefficient to insert an element at the end of a linked list because we need to traverse the entire list starting from the head node to reach the end node to perform the insertion.



Enter your answers into a text file named answers.txt. You can use the editor of your choice for this. You can also create a text file in Eclipse by selecting "New" and then "Untitled Text File" in the "File" menu. Make sure that you save your file. Also make sure that you indicate which question you are answering, e.g. Q1: answer to question 1 Q2: answer to question 2 Q3:...

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

submit 2030 test5C answers.txt