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

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).

Some starter code can be found here.
The API can be found here.
The Java library API can be found here.
You have to put your Test5C class in the eecs2030.test5 package.
You have to use recursion.
You must not use any kind of for statement or while statement.
You must not use the classes Arrays and Collections.
You must not use the methods replace, replaceAll, or replaceFirst from the class String.

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

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.

Question 2 (3 marks)

Prove that the above method terminates.

Question 3 (1 mark)

State the recurrence relation of the above method.

Question 4 (2 marks)

Let f : ℕ → ℕ be defined by f(n) = 3n⁴ + 5n² + 1. Prove that f ∈ O(n⁴). 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 n⁴ as n^4 and n² as n^2 in your answer.

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.

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

EECS2030 Test 5C

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

Instructions

Programming question

Programming question

Other questions

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