package test5; import java.util.List; public class Test5H { private Test5H() { // prevent instantiation } /** * Returns the string made up of the characters in s starting * from index idx and going to the end of s. For * example, * * Test5H.endOf("abcdef", 0) returns "abcdef" * Test5H.endOf("abcdef", 1) returns "bcdef" * Test5H.endOf("abcdef", 2) returns "cdef" * Test5H.endOf("abcdef", 3) returns "def" * * An empty string is returned if idx is greater than or equal to * the length of s. * * @param s * a string * @param idx * the starting index in s * @pre. idx >= 0 * @return the string made up of the characters in s starting from index idx * and going to the end of s */ public static String endOf(String s, int idx) { String result = ""; if (idx >= s.length()) { result = ""; } else { result = s.charAt(idx) + Test5H.endOf(s, idx + 1); } return result; } /** * Returns the sum of the elements in t ignoring elements that * are null. For example, if t is the list * [null, 2, 3, null, 5] then sumIgnoreNull(t) * returns 10. * * The value 0 is returned if t is empty, * or if all elements of t are null. * * @param t * the list to sum (some elements in t might be null) * @return the sum of the elements in t ignoring null values */ public static int sumIgnoreNull(List<Integer> t) { int sum = 0; if (t.isEmpty()) { sum = 0; } else { Integer first = t.get(0); if (first != null) { sum += first; } sum += Test5H.sumIgnoreNull(t.subList(1, t.size())); } return sum; } }
/** * Returns the string made up of the characters of s * in reverse order. * * @param s a string * @return the string made up of the characters of s in reverse order */ public static String reverse(String s) { String rev = ""; if (s.length() < 2) { rev = s; } else { int lastIndex = s.length() - 1; char lastChar = s.charAt(lastIndex); String sMinusLast = s.substring(0, lastIndex); rev = lastChar + X.reverse(sMinusLast); } return rev; }
Prove the above method correct. First, we consider the first base case: the length of s is 0 or 1. The reversal of s is s itself; therefore, the base case is correct. Finally, we consider the recursive case: the length of s is at least 2 and equal to n. We assume that reverse(sMinusLast) correctly returns the string that is the reversal of the first (n - 1) characters of s. Then the recursive case returns the last character of s + the reversal of the first (n - 1) characters of s which is the reversal of s.
Prove that the above method terminates. We define the size of the invocation reverse(s) to be equal to the natural number n, the number of characters in s. Next, we consider the recursive case: reverse(sMinusLast). The size of the invocation is the length of sMinusLast which is n - 1 which is smaller than n (and also a natural number).
Give the recurrence relation of the above method. T(n) = T(n - 1) + constant
Let f : ℕ → ℕ be defined by f(n) = n / 2 + sqrt(n), where sqrt(n) is the square root of n. Then f ∈ O().
Prove your answer to Question 4. 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. Choose M = 1 and m = 4, then: n / 2 + sqrt(n) <= n / 2 + n / 2 <= n because n / 2 >= sqrt(n) for n >= 4 There are many other possibilities for reasonable values of M.