EECS1030M Test 5

Wednesday April 1, 2015, 16:00-17:15
Lab 01
Version E

Programming question

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

package test5;

import java.util.List;

public class Test5E 
{
    /**
     * Returns the maximum of the digits of the given string.
     * 
     * @param digits a string consisting of only digits.
     * @pre. digits.length() > 0 && digits consists of only digits.
     * @return the maximum of the digits of the given string.
     */
    public static int max(String digits)
    {
	int max;
	if (digits.length() == 1)
	{
	    max = digits.charAt(0) - '0';
	}
	else
	{
	    max = Math.max(digits.charAt(0) - '0', Test5E.max(digits.substring(1)));
	}
	return max;
    }
    
    
    /**
     * Returns the length of the concatenation of the strings of the given list.
     * For example, for the list ["this", "is", "the", "last", "test"] the
     * length is 17. 
     * 
     * @param sentence a list of strings.
     * @pre. sentence != null
     * @return the length of the concatenation of the strings of the given list.
     */
    public static int length(List sentence)
    {
	return Test5E.length(sentence, 0);
    }
    
    /**
     * Returns the length of the concatenation of the strings of the 
     * sub list of the given list starting at the given begin index.
     * For example, for the list ["this", "is", "the", "last", "test"] 
     * and the begin index 2, the length is 11. 
     * 
     * @param sentence a list of strings.
     * @pre. sentence != null
     * @param begin the begin index of the sub list
     * @pre. begin >= 0 && begin <= list.size()
     * @return he length of the concatenation of the strings of the 
     * sub list of the given list starting at the given begin index.
     */
    public static int length(List sentence, int begin)
    {
	int length;
	if (begin == sentence.size())
	{
	    length = 0;
	}
	else
	{
	    length = sentence.get(begin).length() + Test5E.length(sentence, begin + 1);
	}
	return length;
    }
}

Other questions

Consider the following method. 
/**
 * Returns n + 4, where n is the given integer.
 *
 * @param n an integer.
 * @pre. n >= 0.
 * @return n + 4.
 */
public static int recursive(int n) 
{
   if (n == 0)
   {
      return 4;
   }
   else if (n == 1)
   {
      return 5;
   }
   else
   {
      return recursive(n - 2) + 2;
   }
}
Question 1

Prove the above method correct.
First, we consider the first base case: n == 0. Since the method returns 4 = 0 + 4, the base case is correct.
Next, we consider the second base case: n == 1. Since the method returns 5 = 1 + 4, the base case is correct.
Finally, we consider the recursive case: n > 1. Note that n-2 >= 0 and, hence, the precondition of the recursive call is satisfied. Assume that the recursive call is correct, that is, recursive(n - 2) returns (n-2) + 4. Then ((n-2) + 4) + 2 = n - 2 + 4 + 2 = n + 4 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)) = n. From the precondition we can conclude that n is a natural number.
Next, we consider the recursive case: n > 1. In that case n-2 is smaller than 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) = 4
T(1) = 6
T(n) = T(n-2) + 8 if n > 1



Question 4

Let f : ℕ → ℕ be defined by f(n) = n^2 + 8 log(n) + 4 (where n^2 denotes n to the power 2). Then f ∈ O(n^2).



Question 5

Prove your answer to Question 4.

We pick M = 8 and F = 13. Let n ≥ 8. Then
n^2 + 8 log(n) + 4 <= n^2 + 8n^2 + 4n^2 <= 13n^2.