Test 4B Feedback
countTo
2 / 2 -is there a suitable base case (from == to)?
2 / 3 -is the recursive case correct?
zipper
2 / 2 -is there a suitable base case (s.isEmpty())?
0 / 1 -are the first and second characters appended together at the front of the string?
0 / 2 -is the recursive invocation correct?
unique
0 / 1 -is there a suitable base case (t.size() < 2)?
0 / 1 -is the first element of the list compared to the second element for equality?
0 / 2 -if the first two elements are equal, is an element removed and unique called correctly?
0 / 1 -if the first two elements are not equal, is unique called correctly?
findZero
0 / 2 -is the list recursively correctly reduced by half?
0 / 1 -is the correct index returned?
--------------------
TA Comments:
-the recursive case of countTo should be:
return from + ", " + countTo(from + 1, to);
-in zipper, you never build the string to return:
public static String zipper(String s, String t) {
if (s.isEmpty()) {
return "";
}
String pre = "" + s.charAt(0) + t.charAt(0);
String post = zipper(s.substring(1), t.substring(1));
return pre + post;
}
--------------------
Unit tester output:
YOUR SUMBISSION FAILED SOME UNIT TESTS
Here is the test output:
java -classpath .:/home/burton/work/teaching/2017F/2030/marking/secEtest4B/_jar/* org.junit.runner.JUnitCore test4.Test4Suite
JUnit version 4.12
..E.E..E.E....E.E.E...E.E.E.E.E.E.E.E.E
Time: 0.118
There were 16 failures:
1) test01b_countTo(test4.Test4BTest)
org.junit.ComparisonFailure: countTo(5, 6) expected:<[5, 6]> but was:<[6, ]>
2) test01c_countTo(test4.Test4BTest)
org.junit.ComparisonFailure: countTo(10, 12) expected:<1[0, 11, 12]> but was:<1[2, , ]>
3) test02b_zipper(test4.Test4BTest)
java.lang.StackOverflowError
4) test02c_zipper(test4.Test4BTest)
java.lang.StackOverflowError
5) test03d_unique(test4.Test4BTest)
java.lang.AssertionError: unique([one, one]) expected:<[one]> but was:<[one, one]>
6) test03e_unique(test4.Test4BTest)
java.lang.AssertionError: unique([one, two, two]) expected:<[one, two]> but was:<[one, two, two]>
7) test03f_unique(test4.Test4BTest)
java.lang.AssertionError: unique([w, w, w, x, y, y, z, z]) expected:<[w, x, y, z]> but was:<[w, w, w, x, y, y, z, z]>
8) test04c_findZero(test4.Test4BTest)
java.lang.AssertionError: expected:<1> but was:<0>
9) test04d_findZero(test4.Test4BTest)
java.lang.AssertionError: expected:<1> but was:<0>
10) test04e_findZero(test4.Test4BTest)
java.lang.AssertionError: expected:<2> but was:<0>
11) test04f_findZero(test4.Test4BTest)
java.lang.AssertionError: expected:<3> but was:<0>
12) test04g_findZero(test4.Test4BTest)
java.lang.AssertionError: expected:<4> but was:<0>
13) test04h_findZero(test4.Test4BTest)
java.lang.AssertionError: expected:<1> but was:<0>
14) test04i_findZero(test4.Test4BTest)
java.lang.AssertionError: expected:<2> but was:<0>
15) test04j_findZero(test4.Test4BTest)
java.lang.AssertionError: expected:<3> but was:<0>
16) test04k_findZero(test4.Test4BTest)
java.lang.AssertionError: expected:<4> but was:<0>
FAILURES!!!
Tests run: 23, Failures: 16
--------------------
Your submission:
package test4;
import java.util.List;
public class Test4B {
private Test4B() {
// empty be design
}
/**
* Returns the string formed by counting starting at <code>from</code>
* up to and including <code>to</code> in increments of 1. Each
* number in the string is separated from the next number by a
* comma and a space.
*
* <pre>
* countTo(1, 1) returns the string equal to "1"
* countTo(5, 6) returns the string equal to "5, 6"
* countTo(10, 12) returns the string equal to "10, 11, 12"
* </pre>
*
* @param from
* the number to count from
* @param to
* the number to count to
* @return the string formed by repeating the specified string n times
* @pre. from is less than or equal to to
*/
public static String countTo(int from, int to) {
// 5 marks
// Your solution must use recursion.
if (from == to){
return ""+to+"";
}
else{
return countTo(from + 1 , to)+ ", ";
}
}
/**
* Given two non-null strings of equal length, returns the string formed by
* alternating characters from s and t. For example:
*
* <pre>
* zipper("", "") returns the empty string
* zipper("a", "1") returns the string "a1"
* zipper("abcd", "1234") returns the string "a1b2c3d4"
* </pre>
*
* @param s a string of length n
* @param t a second string of length n
* @return the string of length 2n formed by alternating characters
* of s and t
*/
public static String zipper(String s, String t) {
// 5 marks
// Your solution must use recursion.
if (s.isEmpty() && t.isEmpty()){
return "";
}
return zipper(s.substring(0) +1,t.substring(0)+1 );
}
/**
* Removes all duplicated strings from a sorted list of strings
* maintaining the sorted order of the strings. If the list contains unique
* strings then the list remains unchanged. For example, if t is the list
* ["a", "b", "c", "d"] then unique(t) would do nothing. If t is the list
* ["w", "w", "w", "x", "y", "y", "z"] then unique(t) would modify t so that
* it became the list ["w", "x", "y", "z"].
*
* @param t
* a sorted list of strings that the method modifies
* so that it contains no duplicated strings (and the list remains in
* sorted order).
*/
public static void unique(List<String> t) {
// 5 marks
// Your solution must use recursion.
// The only List methods you may use are:
// add, get, isEmpty, remove, set, size, and subList
// You may not use any methods from any other utility class.
if (t.isEmpty()){
}
}
/**
* Returns the index of the element equal to zero in the
* specified sorted list. The list t may be sorted in either
* ascending or descending order. The list t is not modified
* by this method.
*
* <p>
* The computational complexity of the method is O(log n) where
* n is the size of the list t.
*
* @param t a sorted list
* @return the index of the element equal to zero
* @pre. the list is sorted in either ascending or descending order
* and the list contains zero
*/
public static int findZero(List<Integer> t) {
// 3 marks
// Your solution must use recursion.
// The only List methods you may use are:
// get, isEmpty, size, and subList
// You may not use any methods from any other utility class.
if (t.isEmpty()){
return 0;
}
if (!t.isEmpty()){
t = t.subList(0, t.size()-1);
}
return 0;
}
}
--------------------
Written answers marking scheme Test4B
A
1 / 1 -returns false?
B
0 / 1 -throws an exception?
C
0 / 3 -is the assumption correct?
D
2 / 2
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 -O(n)?
--------------------
TA Comments
B.
The method throws an IndexOutOfBoundsException because the base case is
not reached.
C.
Assume isEven(s.substring(2)) returns true if s.substring(2) has an even
number of characters, and false otherwise. Note that s.substring(2)
has length equal to s.length() - 2.
D.
If isEven(s.substring(2)) returns true then we know from the assumption
that the string with length equal to s.length() - 2 has an even number of
characters. If s.length() - 2 is even then s.length() is also even;
therefore, the recursive case is correct when it returns true.
If isEven(s.substring(2)) returns false then we know from the assumption
that the string with length equal to s.length() - 2 has an odd number of
characters. If s.length() - 2 is odd then s.length() is also odd;
therefore, the recursive case is correct when it returns false.
E.
Let the size of the problem be n = s.length()
F.
The input to the recursive invocation is s.substring(2) which has length
equal to s.length() - 2 < n; therefore, the recursive case terminates.
G.
O(n)
--------------------
Your submission:
A.
It will keep returning true until it gets to the base case where
the length of the substring is equal to 1 and not 2. So in the end it
will return false. If the string is only of length one, it will return false right away.
B.
It will keep returning true until we go through the entire length of the string. In the end
it will also return true.
C.
We have to assume that the base case is correct. So we have to assume that if(s.length==1) will return false is
correct. Then we have to assume that result=isEven(s.substring(2)); is correct.
D.
s.length>= 2n-s.length
2n-s.length is always less than or equal to s.length.
The recursive case is correct.
E.
To find the size of the problem we look at the elementary operations. From this we can see that the size of this
problem is equal to 4.
F.
T(0)=4
G.
O(log n)
--------------------