For each problem, create a class named ProblemX,
where X is the problem number
(e.g., Problem1.java).
Write corresponding JUnit test classes named
ProblemXTest.
All methods (yes, including helpers) must include proper Javadoc comments describing the (1) purpose of the method, (2) parameters, and (3) return value.
Helper methods should be marked as private.
You do not need to write explicit tests for helper methods because they will be indirectly tested through the driver methods.
For problems containing multiple parts, write the methods inside the same class.
You may not use anything beyond Chapter 2.2. This includes but is not limited to:
Any violation results in a score of 0 on the lab. We have been seeing more and more of these violations recently, so please be careful! Ask your TAs if you are unsure about whether something is allowed.
Please contact a staff member if you are unsure as to whether you're allowed to use something.
This problem has two parts.
Design the recursive String replaceAB(String s) method that
replaces any occurrence of the character "A" with the
character "B" in a given string s.
Design the tail recursive String replaceABTR(String s) method
that solves the same problem as replaceAB, but instead uses
tail recursion. You will need to design a helper method. Remember to include the relevant access modifiers!
Files to Submit:
Problem1.java, Problem1Test.java
In the textbook, we defined recursive addition over natural numbers (integers
≥ 0) using the restricted context (only having isZero,
addOne, subOne, conditionals, and recursion) as
follows:
/**
* Determines whether the given integer is zero.
* @param n a non-negative integer
* @return true if n is zero; false otherwise
*/
private static boolean isZero(int n) {
return n == 0;
}
/**
* Adds one to the given integer.
* @param n a non-negative integer
* @return n + 1
*/
private static int addOne(int n) {
return n + 1;
}
/**
* Subtracts one from the given integer, stopping at zero.
* @param n a non-negative integer
* @return n - 1 if n > 0; otherwise 0
*/
private static int subOne(int n) {
return n <= 0 ? 0 : n - 1;
}
/**
* Recursively adds two non-negative integers.
* @param n a non-negative integer
* @param m a non-negative integer
* @return the sum n + m
*/
static int add(int n, int m) {
if (isZero(m)) {
return n;
} else {
return addOne(add(n, subOne(m)));
}
}
Design the standard recursive int mult(int x, int y) and
int pow(int x, int y) methods that multiply x by
y and raise x to the power of y
respectively. Note that x and y ≥ 0.
Importantly: you are restricted to the context that the textbook uses to write
add. Therefore, you are not allowed to use +,
-, *, or any other method calls.
Hint 1: use add to define mult, and mult
to define pow. Copy the four methods above into your
Problem2.java file.
Hint 2: we will assume \(n^m\) is undefined when \(n=0\) and \(m=0\), so do not test it!
Files to Submit:
Problem2.java, Problem2Test.java
Note: this exercise is worth 5 points of extra credit, but you should still do it if you have time!
Design the tail recursive int compareToTR(String s, String t) method that compares two strings s and t lexicographically (dictionary order).
The method returns -1 if s is lexicographically less than t, +1 if s is lexicographically greater than t, and zero if the two strings are equal.
You will need to design a helper method. Remember to include the relevant access modifiers!
As an extra incentive, if you write this method by recursing over indices (which is more efficient) rather than the lengths of the strings, you will receive an additional 5 points of extra credit.
Warning: you are also not allowed to use any String class methods to solve this problem except for charAt, substring, and length.
Hint 1: break this down into a series of case analyses.
Hint 2: if the two strings are empty, then they are equal. If exactly one of them is empty, then the empty string is lexicographically less than the non-empty string. Otherwise, we should compare their first characters and recurse accordingly.
Hint 3: this is a good exercise in determining if your helper actually needs an accumulator; does it?
Files to Submit: Problem3.java, Problem3Test.java