package test5; import java.util.List; public class Test5D { private Test5D() { } /** * Returns a string of length n formed by alternating the * characters first and second. Some examples: * * Test5D.alternate('*', '-', 0) returns the string "" * Test5D.alternate('*', '-', 1) returns the string "*" * Test5D.alternate('*', '-', 2) returns the string "*-" * Test5D.alternate('*', '-', 3) returns the string "*-*" * Test5D.alternate('*', '-', 4) returns the string "*-*-" * * @param first * the first character of the repeating pattern * @param second * the second character of the repeating pattern * @param n * the length of the desired string * @pre. n >= 0 * @return the string of alternating first and second characters */ public static String alternate(char first, char second, int n) { String s = ""; if (n == 0) { s = ""; } else if (n == 1) { s = "" + first; } else { s = s + first + second + Test5D.alternate(first, second, n - 2); } return s; } /** * Moves the first element f of t down the list * until it reaches the first location in the list where the next element is * greater than or equal to f. For example, if t is * the list: * * [4, 2, 1, 5] then Test5D.moveFirstDown(t) * rearranges the elements in t to [2, 1, 4, 5] (the * 4 moves to the spot immediately before the 5). * * @param t * the list to move the first element of */ public static void moveFirstDown(List<Integer> t) { if (t.size() > 1) { int first = t.get(0); int second = t.get(1); if (first > second) { t.set(0, second); t.set(1, first); Test5D.moveFirstDown(t.subList(1, t.size())); } } } }
/** * Returns true if the character c appears in s, and false otherwise. * * @param s a string * @param c a character to search for in s * @return true if the character c appears in s, and false otherwise. */ public static boolean contains(String s, char c) { int result = false; if (s.isEmpty()) { result = false; } else if (s.charAt(0) == c) { result = true; } else { String t = s.substring(1, s.length()); result = contains(t , c); } return result; }
Prove the above method correct. First, we consider the first base case: s is the empty string. c cannot appear in the empty string; therefore, the base case is correct. Next, we consider the second base case: the first character of s is c. The base case returns true, which is correct. Finally, we consider the recursive case: the length of s is at least 1, and the first character is not c. We assume that contains(t, c) correctly determines if the string equal to s without the first character contains c. Then the recursive case is correct because we know that the first character of s is not c.
Prove that the above method terminates. We define the size of the invocation contains(s, c) to be equal to the natural number n, the number of characters in s. Next, we consider the recursive case: contains(t, n). The size of the invocation is the length of t which is n - 1 which is less than n (and also a natural number)
Give the recurrence relation of the above method. T(n) = T(n - 1) + constant The amount of time it takes to solve a problem of size n is equal to the amount of time it takes to solve a problem of size (n - 1) plus a constant.
Let f : ℕ → ℕ be defined by f(n) = n3 + 11n. 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 = 2 and m = 4, then: n^3 + 11n <= n^3 + n^3 <= 2n^3 because n^3 >= 11n for n >= 4 OR Choose M = 12 and m = 1, then: n^3 + 11n <= n^3 + 11n^3 = 12n^3 for n >= 1 There are many other possibilities for reasonable values of M.