EECS1030M Test 5

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

Programming question

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

package test5;

public class Test5A 
{
    /**
     * Returns the sum of the digits of the given string.
     * The sum of the empty string is 0.
     * 
     * @param digits a string consisting of only digits.
     * @pre. digits consists of only digits.
     * @return the sum of the digits of the given string.
     */
    public static int sum(String digits)
    {
	int sum;
	if (digits.length() == 0)
        {
    	    sum = 0;
	}
	else
	{
	    sum = (digits.charAt(0) - '0') + Test5A.sum(digits.substring(1));
	}
	return sum;
    }
    
    /**
     * Tests whether the given character occurs an even number of 
     * times in the given string.  The number 0 is even.
     * 
     * @param word a word.
     * @pre. word != null
     * @param character a character
     * @return true if the given character occurs an even number of 
     * times in the given string, false otherwise.
     */
    public static boolean even(String word, char character)
    {
	boolean even;
	if (word.length() == 0)
	{
	    even = true;
	}
	else
	{
	    if (word.charAt(0) == character)
	    {
		even = !Test5A.even(word.substring(1), character);
	    }
	    else
	    {
	        even = Test5A.even(word.substring(1), character);
	    }
	}
	return even;
    }
}

Other questions

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

Prove the above method correct.
First, we consider the base case: n == 0. Since the method returns 6 = 6 * 0 + 6, the base case is correct.
Next, we consider the first recursive case: n > 0 and n % 2 == 0. 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 6 * n/2 + 6. Then 2 * (6 * n/2 + 6) - 6 = 6n + 12 - 6 = 6n + 6 and, therefore, this recursive case is correct.
Next, we consider the second recursive case: n > 0 and n % 2 != 0. Note that n-1 >= 0 and, hence, the precondition of the recursive call is satisfied. Assume that the recursive call is correct, that is, recursive(n-1) returns 6 * (n-1) + 6. Then (6 * (n-1) + 6) + 6 = 6n - 6 + 6 + 6 = 6n + 6 and, therefore, this recursice 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 first recursive case: n > 0 and n % 2 == 0. 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.
Finally, we consider the second recursive case: n > 0 and n % 2 != 0. In that case n-1 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) = 5
T(n) = T(n/2) + 11 if n > 0 and n % 2 == 0
T(n) = T(n-1) + 10 if n > 0 and n % 2 != 0



Question 4

Let f : ℕ → ℕ be defined by f(n) = 3n^2 + 8n + 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 = 15. Let n ≥ 8. Then
3n^2 + 8n + 4 <= 3n^2 + 8n^2 + 4n^2 <= 15n^2.