1. The idea is to recursively examine the first character of the string, adding 1 to the total if the character is an 'a'.
The easiest base case to use is the empty string, in which case the count is 0.
public class Count
{
public static int countA(String s)
{
int result = 0;
// base case: empty string
if(s.isEmpty())
{
result = 0;
}
// recursive case:
// 1. count the first character (1 for an 'a' and 0 otherwise)
// 2. remove the first character from the string (creating a new string)
// 3. recursively count the new string
else
{
char first = s.charAt(0);
String t = s.substring(1, s.length());
if(first == 'a')
{
result = 1 + Count.countA(t);
}
else
{
result = Count.countA(t);
}
}
return result;
}
public static void main(String[] args)
{
System.out.println(Count.countA(""));
System.out.println(Count.countA("bcdedfg"));
System.out.println(Count.countA("a"));
System.out.println(Count.countA("bcda"));
System.out.println(Count.countA("abcd"));
System.out.println(Count.countA("aabcd"));
System.out.println(Count.countA("bcaad"));
System.out.println(Count.countA("bacad"));
System.out.println(Count.countA("bacda"));
}
}
b) Termination: Let the size of the problem be the length of the string.
Then the recursive invocation is always smaller than the original invocation
because we always remove the first character of the string before making the
recursive invocation.
2. There are at least two ways to solve this problem. Assume for now that the original list always holds a valid expression. The shortest valid expression is a single digit (which establishes the base case). Every other valid expression always starts with a digit followed by a plus or minus sign (which establishes the recursive case for the first solution).
The first solution recursively examines the first two elements of the list. If the first element is a digit and the second element is a plus or minus sign then the method removes the first two elements from the list and recursively examines the rest of the list.
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class MathList
{
public static boolean isDigit(Character c)
{
String s = c.toString();
return s.matches("\\d");
}
public static boolean isOperator(Character c)
{
String s = c.toString();
return s.equals("+") || s.equals("-");
}
public static boolean isValid(List<Character> s)
{
boolean result = false;
// base case: list is empty (or null)
if (s == null || s.isEmpty())
{
}
// base case: list of one element
else if (s.size() == 1)
{
result = MathList.isDigit(s.get(0));
}
else
{
Character first = s.get(0);
Character second = s.get(1);
if (MathList.isDigit(first) && MathList.isOperator(second))
{
LinkedList<Character> t = new LinkedList<Character>(s);
t.remove();
t.remove();
result = MathList.isValid(t);
}
}
return result;
}
public static void main(String[] args)
{
// valid
List<Character> s1 = Arrays.asList('1');
List<Character> s2 = Arrays.asList('2', '+', '3');
List<Character> s3 = Arrays.asList('0', '-', '1', '+', '2', '-', '5');
// invalid
List<Character> s4 = Arrays.asList();
List<Character> s5 = Arrays.asList('-');
List<Character> s6 = Arrays.asList('9', '+', '3', '-');
List<Character> s7 = Arrays.asList('+', '7', '-');
System.out.println(MathList.isValid(s1));
System.out.println(MathList.isValid(s2));
System.out.println(MathList.isValid(s3));
System.out.println(MathList.isValid(s4));
System.out.println(MathList.isValid(s5));
System.out.println(MathList.isValid(s6));
System.out.println(MathList.isValid(s7));
}
}
a) Correctness: The first base case is obviously correct (null list or empty list). The second base case is correct because the list of length 1 is valid if and only if the list contains a digit. Assume that the recursive invocation MathList.isValid(t) correctly determines if t is valid; then the recursive invocation is correct because the first two characters of the original list were a digit followed by an operator, which is the start of every valid expression.
b) Termination: Let the size of the problem be the length of the list. Then the recursive invocation is always smaller than the original because we always remove two elements from the list before each recursive invocation.
A second solution is to recursively inspect the first and last character of the
list. The first time the method is called, it checks if the first and last
element are digits; if so, then the method removes the first and last elements
from the list, and then checks (recursively or not) if the first and last
elements are operators. There are at least two ways to implement this method.
The first approach uses a boolean parameter to decide if the method is checking
for digits or checking for operators.
// if checkForDigits is true then the method checks for digits; otherwise it checks for operators
public static boolean isValid2(List<Character> s, boolean checkForDigits)
{
boolean result = false;
// base case: list is empty (or null)
if (s == null || s.isEmpty())
{
}
// base case: list of one element and checking for digits
else if (s.size() == 1 && checkForDigits)
{
result = MathList.isDigit(s.get(0));
}
// base case: list of one element and checking for operators
else if (s.size() == 1 && !checkForDigits)
{
result = MathList.isOperator(s.get(0));
}
else
{
Character first = s.get(0);
Character last = s.get(s.size() - 1);
if(checkForDigits && MathList.isDigit(first) && MathList.isDigit(last))
{
LinkedList<Character> t = new LinkedList<Character>(s);
t.remove();
t.remove(t.size() - 1);
result = MathList.isValid2(t, false);
}
else if(!checkForDigits && MathList.isOperator(first) && MathList.isOperator(last))
{
LinkedList<Character> t = new LinkedList<Character>(s);
t.remove();
t.remove(t.size() - 1);
result = MathList.isValid2(t, true);
}
}
return result;
}
The second approach uses one recursive method to check for digits and another recursive method to check for operators; the two methods call each other.
public static boolean isValid3(List<Character> s)
{
boolean result = false;
// base case: list is empty (or null)
if (s == null || s.isEmpty())
{
}
// base case: list of one element
else if (s.size() == 1)
{
result = MathList.isDigit(s.get(0));
}
else
{
Character first = s.get(0);
Character last = s.get(s.size() - 1);
if(MathList.isDigit(first) && MathList.isDigit(last))
{
// starts and ends with a digit; now check for operators
LinkedList<Character> t = new LinkedList<Character>(s);
t.remove();
t.remove(t.size() - 1);
result = MathList.isValid3Operator(t);
}
}
return result;
}
private static boolean isValid3Operator(List<Character> s)
{
boolean result = false;
if(s == null)
{
}
else if(s.size() == 1)
{
result = MathList.isOperator(s.get(0));
}
else
{
Character first = s.get(0);
Character last = s.get(s.size() - 1);
if(MathList.isOperator(first) && MathList.isOperator(last))
{
// starts and ends with an operator; now check for digits
LinkedList<Character> t = new LinkedList<Character>(s);
t.remove();
t.remove(t.size() - 1);
result = MathList.isValid3(t);
}
}
return result;
}
3. The empty array and the array of length 1 are sorted by definition. Longer arrays might be sorted if a[0] <= a[1]; if a[0] <= a[1] then remove the first element from the array and recursively check the remaining elements.
import java.util.Arrays;
public class Sorted
{
public static boolean isSorted(int[] a)
{
boolean result = false;
if(a.length < 2)
{
result = true;
}
else
{
if(a[0] <= a[1])
{
result = Sorted.isSorted(Arrays.copyOfRange(a, 1, a.length));
}
}
return result;
}
public static void main(String[] args)
{
// sorted
int[] a0 = {};
int[] a1 = {1};
int[] a2 = {1, 2};
int[] a3 = {1, 2, 3};
// not sorted
int[] a4 = {2, 1, 3, 4};
int[] a5 = {2, 3, 4, 5, 1};
System.out.println(Sorted.isSorted(a0));
System.out.println(Sorted.isSorted(a1));
System.out.println(Sorted.isSorted(a2));
System.out.println(Sorted.isSorted(a3));
System.out.println(Sorted.isSorted(a4));
System.out.println(Sorted.isSorted(a5));
}
}
a) Correctness: The base cases are true by definition. Assume that the recursive call correctly determines if the array with elements a[1] to a[a.length - 1] is sorted; then the recursive case is correct because the first element of the array is smaller than or equal to the second element.
b) Termination: Let the size of the problem be the length of the array. Then
the recursive invocation is smaller than the original invocation because we
remove one element from the array before making the recursive invocation.
4. This problem is very similar to problem 2. The shortest valid string is "a", which partly establishes the base case. You can recursively check the string from left to right using a single method that takes only a single string as an argument if you make sure that the string always begins with an "a" (if you remove one character at a time, you have deal with the case that a valid string might start with a "bb"). To make sure that a string always begins with an "a", you remove the first character if the string starts with "aa" and you remove the first three characters if the string starts with "abb". This works because a "bb" must be the end of the string or followed by an "a".
public class AB
{
public static boolean isValid(String s)
{
boolean result = false;
if(s.isEmpty())
{
}
else if(s.length() == 1)
{
result = s.equals("a");
}
else if(s.length() == 3)
{
result = s.equals("abb");
}
else
{
if(s.startsWith("aa"))
{
String t = s.substring(1, s.length());
result = AB.isValid(t);
}
else if(s.startsWith("abb"))
{
String t = s.substring(3, s.length());
result = AB.isValid(t);
}
}
return result;
}
public static void main(String[] args)
{
// valid
System.out.println(AB.isValid("a"));
System.out.println(AB.isValid("aa"));
System.out.println(AB.isValid("abb"));
System.out.println(AB.isValid("abba"));
System.out.println(AB.isValid("aaaaaabbabbaaaabb"));
// not valid
System.out.println(AB.isValid(""));
System.out.println(AB.isValid("b"));
System.out.println(AB.isValid("ab"));
System.out.println(AB.isValid("aaaaabbb"));
System.out.println(AB.isValid("aaacbb"));
}
}