EECS1030M Test 5

Wednesday April 1, 2015, 13:00-14:15
Lab 02
Version B

Programming question

Implement the Test5B class. A skeleton can be found here. The API can be found here. 

package test5;

import java.util.List;

public class Test5B 
{
    /**
     * Returns the conversion of the given string by replacing each
     * 0 (zero) with O (capital o) and each 1 with I.
     * 
     * @param binary a string of 0s and 1s
     * @pre. binary only consists of 0s and 1s
     * @return the conversion of the given string by replacing each
     * 0 (zero) with O (capital o) and each 1 with I.
     */
    public static String convert(String binary)
    {
	String convert;
	if (binary.length() == 0)
	{
	    convert = "";
	}
	else
	{
	    convert = (binary.charAt(0) == '0' ? "O" : "I") + Test5B.convert(binary.substring(1));
	}
	return convert;
    }
    
    /**
     * Returns the string consisting of the characters of the given list.
     * 
     * @param letters a list of characters
     * @pre. letters != null
     * @return the string consisting of the characters of the given list.
     */
    public static String concat(List letters)
    {
	return Test5B.concat(letters, 0);
    }
    
    /**
     * Returns the string consisting of the characters of the sub list
     * of the given list, beginning at the given index.
     * 
     * @param letters a list of characters
     * @pre. list != null
     * @param begin the begin index of the sub list
     * @pre. begin >= 0 && begin <= list.size()
     * @return the string consisting of the characters of the sub list
     * of the given list, beginning at the given index.
     */
    public static String concat(List letters, int begin)
    {
	String concat;
	if (letters.size() == begin)
	{
	    concat = "";
	}
	else
	{
	    concat = letters.get(begin) + Test5B.concat(letters, begin + 1);
	}
	return concat;
    }
}

Other questions

Consider the following method. 
/**
 * Returns 6n + 6, where n is the given integer.
 *
 * @param n an integer.
 * @pre. 0 <= n && n <= 100.
 * @return 6n + 6.
 */
public static int recursive(int n) 
{
   if (n == 100)
   {
      return 606;
   }
   else if (n == 99)
   {
      return 600;
   }
   else
   {
      return recursive(n + 2) - 12;
   }
}
Question 1

Prove the above method correct.
First, we consider the first base case: n == 100. Since the method returns 606 = 6 * 100 + 6, the base case is correct.
Next, we consider the second base case: n == 99. Since the method returns 600 = 6 * 99 + 6, the base case is correct.
Finally, we consider the recursive case: 0 <= n && n <= 100 and n != 100 and n != 99. Note that 0 <= n+2 && n+2 <= 100 and, hence, the precondition of the recursive call is satisfied. Assume that the recursive call is correct, that is, recursive(n+2) returns 6 * (n+2) + 6. Then (6 * (n+2) + 6) - 12 = 6n + 12 + 6 - 12 = 6n + 6 and, therefore, this recursive case is correct.



Question 2

Prove that the above method terminates.
We define the size of the invocation recursive(n) by size(recursive(n)) = 100-n. From the precondition we can conclude that 100-n is a natural number.
Next, we consider the recursive case: 0 <= n && n <= 100 and n != 100 and n != 99. In that case 100-(n+2) is smaller than 100-n and, hence, the size of the recursive invocation is smaller than the size of the original invocation.



Question 3

Give the recurrence relation of the above method. You do not have solve the recurrence relation.
T(0) = 5
T(1) = 7
T(n) = T(n-2) + 9 if n >= 2



Question 4

Let f : ℕ → ℕ be defined by f(n) = 8n + 3 log(n) + 4. Then f ∈ O(n).



Question 5

Prove your answer to Question 4.

We pick M = 4 and F = 15. Let n ≥ 4. Then
8n + 3 log(n) + 4 <= 8n + 3n + 4n <= 15n.