EECS1030M Test 5

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

Programming question

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

package test5;

import java.util.List;

public class Test5F 
{
    /**
     * Returns the number of a's in the given string.
     * 
     * @param word a string
     * @pre. word != null
     * @return the number of a's in the given string.
     */
    public static int numberOfAs(String word)
    {
	int number;
	if (word.length() == 0)
	{
	    number = 0;
	}
	else
	{
	    number = word.charAt(0) == 'a' ? 1 : 0;
	    number += Test5F.numberOfAs(word.substring(1));
	}
	return number;
    }
    
    /**
     * Tests whether all strings of the given list have the same
     * length.
     * 
     * @param sentence a list of strings
     * @pre. sentence != null
     * @return true if all strings of the given list have the same
     * length, false otherwise.
     */
    public static boolean sameLength(List sentence)
    {
	boolean same;
	if (sentence.size() <= 1)
	{
	    same = true;
	}
	else
	{
	    same = sentence.get(0).length() == sentence.get(1).length()
	        && Test5F.sameLength(sentence.subList(1, sentence.size()));
	}
	return same;
    }
}

Other questions

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

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



Question 4

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



Question 5

Prove your answer to Question 4.

We pick M = 4 and F = 13. Let n ≥ 4. Then
8n + 4/n + 3 <= 8n + 4n + n <= 13n.