Test 4A Feedback
repeat
2 / 2 -is there a suitable base case (n == 1)?
3 / 3 -is the recursive case correct?
isPalindrome
2 / 2 -is there a suitable base case (s.length() < 2)?
1 / 1 -are the first and last characters of the string compared for equality?
2 / 2 -is the recursive invocation correct?
partition
1 / 1 -is there a suitable base case (t.size() < 2)?
1 / 1 -is the first element of the list compared to 0?
1 / 1 -if yes, is partitioned called correctly?
1 / 1 -if no, is the first element moved to the end of the list?
1 / 1 -and is partition called correctly?
findZero
2 / 2 -is the list recursively correctly reduced by half?
1 / 1 -is the correct index returned?
--------------------
TA Comments:
--------------------
Unit tester output:
Passed all unit tests.
--------------------
Your submission:
package test4;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Test4A {
private Test4A() {
// empty by design
}
/**
* Returns the string formed by repeating the specified string n times; each
* repetition of s is separated by a comma followed by space.
*
* <pre>
* repeat("cat", 1) returns the string equal to "cat"
* repeat("rat", 2) returns the string equal to "rat, rat"
* repeat("la", 3) returns the string equal to "la, la, la"
* </pre>
*
* @param s
* the string to be repeated
* @param n
* the number of times to repeat s
* @return the string formed by repeating the specified string n times
* @pre. n is greater than zero
*/
public static String repeat(String s, int n) {
// 5 marks
// Your solution must use recursion.
if (n == 1) {
return s;
}
return s + ", " + Test4A.repeat(s, n-1);
}
/**
* Returns true if the specified string is a palindrome. A palindrome
* is a string that is spelled the same backwards and forwards. The
* empty string is a palindrome.
*
* <pre>
* isPalindrome("a") returns true
* isPalindrome("at") returns false
* isPalindrome("tat") returns true
* isPalindrome("refer") returns true
* isPalindrome("refers") returns false
* </pre>
*
* @param s a string
* @return true if the specified string is a palindrome, and false otherwise
*/
public static boolean isPalindrome(String s) {
// 5 marks
// Your solution must use recursion.
int length = s.length();
if (length == 0) {
return true;
}
if (s.charAt(0) == s.charAt(length - 1)) {
if (length == 1) {
return true;
}
return Test4A.isPalindrome(s.substring(1, length-1));
}
return false;
}
/**
* Re-orders the elements of the argument list t so that
* all of the negative elements of t are in the front part
* of the list and all of the positive elements of t are
* in the back part of the list. If the list contains zero
* or one elements then the list is not modified. There is
* no guarantee of the ordering of the positive elements
* or of the negative elements.
*
* <p>
* Zero is considered to be a positive number for the purposes
* of this method.
*
* <p>
* For example, a possible solution results in the following:
* </p>
*
* <pre>
* if t is [] then partition(t) makes t []
* if t is [1] then partition(t) makes t [1]
* if t is [-1, 2] then partition(t) makes t [-1, 2]
* if t is [2, -1] then partition(t) makes t [-1, 2]
* if t is [8, -2, 1] then partition(t) makes t [-2, 1, 8]
* if t is [1, -5, -9, 4] then partition(t) makes t [-5, -9, 4, 1]
* if t is [-3, 7, -1, 3, -5] then partition(t) makes t [-3, -1, -5, 7, 3]
* </pre>
*
* @param t a list of integers
*/
public static void partition(List<Integer> 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.size() < 2) {
return;
}
Test4A.partition(t.subList(1, t.size()));
int first = t.get(0);
if (first >= 0) {
t.remove(0);
t.add(first);
}
}
/**
* 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.
int length = t.size();
int mid = length/2;
int midElem = t.get(mid);
if (midElem == 0) {
return length/2;
}
int precElem = t.get(mid-1);
if (midElem > 0) {
if (midElem > precElem){
return Test4A.findZero(t.subList(0, mid));
}
return mid + 1 + Test4A.findZero(t.subList(mid+1, length));
}
if(midElem > precElem) {
return mid + 1 + Test4A.findZero(t.subList(mid+1, length));
}
return Test4A.findZero(t.subList(0, mid));
}
}
--------------------
Written answers marking scheme
A
1 / 1 -is the correct precondition given?
B
1 / 1 -is there a suitable explanation?
C
3 / 3 -is the assumption correct?
D
2 / 2
E
2 / 2 -is the size of the problem defined correctly?
F
2 / 2 -is the recursive call shown to solve a smaller sized problem?
G
1 / 1 -O(n)?
--------------------
TA Comments
--------------------
Your submission:
A.
If the precondition would be that num >= 0 then the base case would be
correct.
B.
The base case would be true because any number that has one digit is less
than 10. Therefore if evenNumberOfDiits is called on any number from 0 to
9, then it would be false; which is what the method returns.
C.
Assume that the base case is correct and that evenNumberOfDigits(num / 10)
will return the correct value for the number of digits - 1.
D.
Therefore, if the number of digits is even then evenNumberOfDigits(num / 10)
will return false, because num / 10 has an odd number of digits. This means
that !evenNumberOfDigits(num / 10) would return true if the num has an even
number of digits. By extension, if num has an odd number of digits, then
evenNumberOfDigits(num / 10) will return true because num / 10 has an even
number digits, which means !evenNumberOfDigits(num / 10) will return true.
E.
The size of the problem is log_10(num)
F.
The size of the recursive invocation of num/10 is less than the size of num
because log_10(num/10) = log_10(num) - 1 and the base case has been proven.
G.
The Big-O copmlexity of O(n), where n refers to the number of digits in num.
--------------------