Test 4C Feedback
doubler
2 / 2 -is there a correct base case(s) (and no incorrect base cases)?
1 / 1 -is the first character (or last character) of the string repeated?
1 / 1 -is the recursive invocation correct?
1 / 1 -is the correct string returned?
flipCase
1 / 1 -is there a correct base case(s) (and no incorrect base cases)?
1 / 1 -is the first (or last) character of the string examined for case?
1 / 1 -is the first (or last) character converted to the opposite case?
1 / 1 -is the recursive invocation correct?
1 / 1 -is the correct string returned?
repair
1 / 1 -is the base case where t is the empty list correct?
1 / 1 -is the base case where t is list of size 1 correct?
1 / 1 -are the first (or last) two elements of the list compared for order?
1 / 1 -are the first (or last) two elements swapped if they are out of order?
1 / 1 -is the recursive invocation correct?
wheresWaldo
2 / 2 -is bisection used in an attempt to solve the problem (no incrementing
of locA or decrementing of locB is allowed; the solution must only use
bisection)
0 / 1 -is Waldo's actual location returned?
--------------------
TA Comments:
-good attempt at wheresWaldo
--------------------
Unit tester output:
YOUR SUMBISSION FAILED SOME UNIT TESTS
Here is the test output:
java -classpath .:/home/burton/work/teaching/2017F/2030/marking/secEtest4C/_jar/* org.junit.runner.JUnitCore test4.Test4Suite
JUnit version 4.12
...........................E
Time: 0.017
There was 1 failure:
1) test04h_wheresWaldo(test4.Test4CTest)
java.lang.StackOverflowError
FAILURES!!!
Tests run: 27, Failures: 1
--------------------
Your submission:
package test4;
import java.util.List;
public class Test4C {
private Test4C() {
// empty by design
}
public static void main(String[] args) {
System.out.println(Test4C.flipCase("hiH"));
}
/**
* Returns the string formed by repeating each character in
* the specified string. For example:
*
* <pre>
* doubler("") returns the string equal to ""
* doubler("a") returns the string equal to "aa"
* doubler("xy") returns the string equal to "xxyy"
* doubler("big") returns the string equal to "bbiigg"
* doubler("EECS") returns the string equal to "EEEECCSS"
* </pre>
*
* @param s a string
* @return the string formed by repeating each character in
* the specified string
*/
public static String doubler(String s) {
// 5 marks
// Your solution must use recursion.
if (s.isEmpty())
return "";
return s.substring(0, 1) + s.substring(0, 1) + Test4C.doubler(s.substring(1));
}
/**
* Returns a string where the case of each letter is flipped compared to the
* corresponding letter in s. The empty string is returned if s is equal
* to the empty string. For example:
*
* <pre>
* flipCase("") returns the string equal to ""
* flipCase("a") returns the string equal to "A"
* flipCase("A") returns the string equal to "a"
* flipCase("abCd") returns the string equal to "ABcD"
* flipCase("CAMELcASE") returns the string equal to "camelCase"
* </pre>
*
* @param s
* a string consisting of English letter characters
* @return a string where the case of each letter is flipped compared to the
* corresponding letter in s
*/
public static String flipCase(String s) {
// 5 marks
// Your solution must use recursion.
// You should use the methods in java.lang.Character to help
// you implement this method. In particular, you may use:
// Character.isLowerCase
// Character.isUpperCase
// Character.toLowerCase
// Character.toUpperCase
if (s.isEmpty())
return "";
char first = s.charAt(0);
if (Character.isLowerCase(first)){
char upper = Character.toUpperCase(first);
return upper + Test4C.flipCase(s.substring(1));
}
else{
char lower = Character.toLowerCase(first);
return lower + Test4C.flipCase(s.substring(1));
}
}
/**
* Sorts the elements of the list t so that the elements are
* in ascending order. A precondition of this method is that t
* must be already sorted in ascending order except that adjacent
* pairs of elements in t may be out of order. Consider the following
* almost sorted lists:
*
* <pre>
* [1, 0] 1, 0 is out of order
* [0, 2, 1] 2, 1 is out of order
* [0, 2, 1, 3] 2, 1 is out of order
* [0, 2, 1, 4, 3] 2, 1 and 4, 3 are out of order
* [0, 1, 3, 2, 4] 3, 2 is out of order
* </pre>
*
* <p>
* This method switches the positions of the out-of-order
* adjacent elements thus repairing the list so that it is
* in sorted order.
*
* @param t a list of almost sorted elements
* @pre. t is sorted in ascending order except that adjacent
* pairs of elements may be out of order
*/
public static void repair(List<Integer> t) {
// 5 marks
// Your solution must use recursion.
// The only List methods you may use are:
// get, isEmpty, set, size, and subList
// You may not use any methods from any other utility class.
if (!t.isEmpty()){
if (t.size() > 1){
Integer first = t.get(0);
Integer second = t.get(1);
Integer newf = t.get(1);
Integer news = t.get(0);
if (first > second){
t.set(0, newf);
t.set(1, news);
}
}
Test4C.repair(t.subList(1, t.size()));
}
}
/**
* Returns the location of Waldo given two guesses of Waldo's location.
* Waldo's location is an integer value somewhere between
* Integer.MIN_VALUE and Integer.MAX_VALUE. Only Waldo knows
* Waldo's location, and Waldo is not willing to give his exact
* location to anyone; however, Waldo is willing to tell a
* client which of two guesses is closer to his location (see the closer method
* in the Waldo class).
*
* <p>
* This method can find Waldo's location using 32 or fewer recursive calls
* (i.e., it does not check every possible location for Waldo).
*
* @param waldo a reference to a Waldo object
* @param locA a guess of Waldo's location
* @param locB a guess of Waldo's location
* @return Waldo's exact location
* @pre. locA is less than or equal to locB
*/
public static int wheresWaldo(Waldo waldo, int locA, int locB) {
// 3 marks
// Your solution must use recursion.
int closer = waldo.closer(locA, locB);
if (closer == 0)
return (int)((locB + locA) / 2);
if (closer == -1 && (locB > Integer.MIN_VALUE))
return Test4C.wheresWaldo(waldo, locA, locB-1);
if (closer == 1 && (locA < Integer.MAX_VALUE))
return Test4C.wheresWaldo(waldo, locA+1, locB);
return 0;
}
}
--------------------
Written answers marking scheme Test4C
A
0.5 / 1 - x > y && y > 1 ?
B
1 / 1 -is there a suitable explanation?
C
0 / 3 -is the assumption correct?
D
2 / 2 -question is poorly written
E
0 / 2 -is the size of the problem defined correctly?
F
0 / 2 -is the recursive call shown to solve a smaller sized problem?
G
0 / 1 - y > Math.sqrt(x) ?
--------------------
TA Comments
A.
x > y && y > 1
B.
If (x % y == 0) is true, then y is a divisor of x that is not equal
to x nor 1; therefore, x is not a prime number. Base case 2 returns
false, which is correct.
C.
Assume isPrime(x, y + 1) returns true if x is prime and false otherwise.
D.
This question is poorly written; all students will receive 2 marks
regardless of their answer.
The recursive case runs when the integers 2 through y are not divisors
of x and y is less than 0.5 * x. We still need to check if any of the
values y + 1 through x / 2 are divisors of x, which is accomplished
using the assumption from Part C.
E.
Let the size be n = 0.5x - y where 0.5x is the integer equal to
0.5 * x rounded up to the nearest integer. n is a natural number
(assuming that the precondition from A is included).
F.
The size of the recursive invocation is
0.5x - (y + 1) = 0.5x - y - 1 = n - 1 < n;
therefore, the recursive case terminates.
G.
The largest divisor of x that is not equal to x is the integer equal to
the square root of x (assuming such an integer exists). Therefore,
the condition for base case 1 could be:
if (y > Math.sqrt(x))
--------------------
Your submission:
A. X >= Y needs to be true to ensure that base case 2 is correct.
B. X % Y = 0 when X is divisible by Y (renainder=0), which cannot occur if X is a
prime number. So the method correctly outputs false.
C. We should assume that the size of the recursive call is smaller than the size of
the origional call and that it eventually terminates.
D. In the recursive call, Y is increased by 1. This makes the difference between X
and Y smaller and smaller until it hits a base case - and so the method terminates and the recursive is correct.
E. T(n) = T(n-1) + C , T(0)=5(=C)
F. T(n-1)=T((n-1)-1)... until a base case terminates the method.
G. X % X == 0 and X % 1 = 0, second if goes first
--------------------