Problems

1. Design the boolean isPalindromeTR(String s) tail recursive method, which receives a string and determines if it is a palindrome. Recall that a palindrome is a string that is the same backwards as it is forwards (e.g., "racecar").

   Warning: Do not use a (character) array, StringBuilder, StringBuffer, or similar, to solve this problem. It must be naturally recursive.

   Files to Submit: Problem1.java, Problem1Test.java

2. This problem has two parts.

   1. The hyperfactorial of a number, namely \(H(n)\), is the value of \(1^1 \cdot 2^2 \cdot \ldots \cdot n^n\). Because the resulting values are outrageously large, use the long datatype. Design the standard recursive long hyperfactorial(long n) method, which receives a long integer \(n\) and returns its hyperfactorial.

   2. Design the tail recursive long hyperfactorialTR(long n) method that uses tail recursion to solve the same problem. You will need to design a private static helper method.

   Files to Submit: Problem2.java, Problem2Test.java

3. This problem has two parts.

   1. The subfactorial of a number, namely \(!n\), is the number of permutations of \(n\) objects such that no object appears in its natural spot. For example, \(!3 = 2\). We define subfactorial recursively as:

      \[ !n = \begin{cases} 1 & \text{if } n = 0\\ 0 & \text{if } n = 1\\ (n-1)\cdot\big(!(n-1) + !(n-2)\big) & \text{if } n > 1 \end{cases} \]

      Design the standard recursive long subfactorial(long n) method, which receives a long integer \(n\) and returns its subfactorial. We once again use the long datatype instead of int to handle larger values.

   2. Design the tail recursive long subfactorialTR(long n) method that uses tail recursion to solve the same problem. You will need to design a private static helper method.

   Hint: if you are getting stuck with the tail recursive version, refer back to the Fibonacci tail recursive method from the textbook!

   Files to Submit: Problem3.java, Problem3Test.java

4. This problem has two parts.

   1. Design the standard recursive String collatz(int n) method, which receives a positive integer and returns the Collatz sequence, as a string, for that integer:

      \[ \texttt{collatz(n)} = \begin{cases} \texttt{1} & \text{if } n = 1\\ \texttt{collatz(n / 2)} & \text{if } n \text{ is even}\\ \texttt{collatz(3 * n + 1)} & \text{if } n \text{ is odd} \end{cases} \]

      The sequence continues until it reaches 1. For example, collatz(5) returns "5,16,8,4,2,1". The last number cannot have a comma afterwards.

   2. Design the tail recursive String collatzTR(int n) method that uses tail recursion to solve the same problem. You will need to design a private static helper method.

   Files to Submit: Problem4.java, Problem4Test.java

5. This problem has two parts.

   A parenthesized string is a string enclosed by parentheses. For example, "(abc)pqr(de)" contains two parenthesized strings: "abc" and "de".

   Assume there are no nested parentheses, all parentheses are balanced, and each parenthesized string contains at least one character.

   1. Design the standard recursive String collectParenthesizedStrings(String s) method, which returns a single string containing all parenthesized substrings. Do not include a delimiter. For example, collectParenthesizedStrings("(abc)pqr(de)") returns "abcde".

   2. Design the tail recursive String collectParenthesizedStringsTR(String s) method that uses tail recursion to solve the same problem. You will need to design a private static helper method.

   Files to Submit: Problem5.java, Problem5Test.java

6. Design the tail recursive char findLastNonDigitCharTR(String s) method that returns the last character in the string that is not a digit. If no such character exists, return the NUL character, i.e., '\0'.

   Files to Submit: Problem6.java, Problem6Test.java

7. Consider the following data definitions:

         A BooleanLiteral is one of:
           - "T"
           - "F"
   
         A BooleanLiteralAtom is one of:
           - BooleanLiteral
           - "!" + BooleanLiteral
   
         A BooleanExpression is one of:
           - BooleanLiteralAtom
           - BooleanExpression + "&" + BooleanExpression
           - BooleanExpression + "|" + BooleanExpression
       

   We evaluate a BooleanExpression as follows: when we encounter a "!", flip the immediately-following boolean value. When we encounter a "&", take the left boolean value and recurse on the right side, then return the logical AND of the two values. When we encounter a "|", take the left boolean value and recurse on the right side, then return the logical OR of the two values.

   For example, evaluating "!T&F|T" means we first negate T to get F, then we encounter &, so we recurse on the rest of the string to evaluate "F|T". We encounter |, so we recurse on the rest of the string to evaluate "T", which resolves to true. As the recursion unwinds, we evaluate false || true to get true, then false && true to get false.

   This order of evaluation is right-associative, i.e., it's as if "!T&F|T" has implicit parentheses as ("!T")&("F"|("T")).

   Design the standard recursive boolean evaluateBooleanExpression(String expr) method that evaluates a given boolean expression according to the above data definition. Therefore, you may assume that the input is always a valid BooleanExpression.

   Hint 1: this problem is pretty difficult to solve, and we would strongly recommend you not wait until the last minute to start working on it.

   Hint 2: consider this a case analysis on the length of the string: if the string is length 1, what do you know about it? If it is length 2, what do you know about it? If it has more than 2 characters, what do you know about it?

   Hint 3: obviously, the hardest part of this problem is handling the case where there are more than 2 characters, e.g., with a binary operator, because there's the inherent possibility of a negated BooleanLiteral, which must be handled prior to the binary operator evaluation.

   Files to Submit: Problem7.java, Problem7Test.java