Problems

1. (8 points) Design the String[] fizzBuzz(int min, int max) method that iterates over the interval \(i \in [\mathit{min}, \mathit{max}]\) (you may assume \(\mathit{max} \geq \mathit{min}\)) and returns an array containing strings that meet the following criteria:

   • If i is divisible by 3, insert "Fizz".

   • If i is divisible by 5, insert "Buzz".

   • If i is divisible by both 3 and 5, insert "FizzBuzz".

   • Otherwise, insert "i", where i is the current number.

   Take the following examples as motivation.

   fizzBuzz(1, 12)  => {"1", "2", "Fizz", "4", "Buzz",
                        "Fizz", "7", "8", "Fizz", "Buzz",
                        "11", "Fizz"}
   fizzBuzz(15, 18) => {"FizzBuzz", "16", "17", "Fizz"}
     

   Files to Submit: Problem1.java, Problem1Test.java

2. (12 points) Design the standard recursive boolean canSum(int[] A, int t) method that, when given an array of integers \(A\) and a target \(t\), determines whether or not there exists a group of numbers in \(A\) that sum to \(t\). For example, if \(A=\{2, 4, 10, 8\}\) and \(t=9\), then canSum returns false because there is no possible selection of integers from \(A\) that sum to \(9\). On the other hand, if \(A=\{3, 7, 4, 5, 9\}\) and \(t=8\), then we return true because \(3+5=8\). If \(A=\{2, 4, 2, 1, 5, 4\}\) and \(t=9\), then we return true because \(4+1+4\), but also \(4+5=9\), \(5+4=9\), and \(4+1+2+2=9\).

   Note: The value of \(t\) can be negative, zero, or positive, so don't have a base case that assumes otherwise.

   Hint 1: Our solution is four lines long—yours should be around the same length.

   Hint 2: Make two recursive calls! If at least one of them returns true, then you have your answer. The questions are, what makes your method return true and what makes the recursive calls different?

   Warning: There is a solution to this problem that uses an advanced technique called dynamic programming. Do not use this technique; the problem states that you must solve this using standard recursion.

   Files to Submit: Problem2.java, Problem2Test.java

3. (12 points) The correlation coefficient \(r\) is a measure of the strength and direction of a linear relationship between two variables \(x\) and \(y\). The value of \(r\) is always between \(-1\) and \(1\). When \(r > 0\), there is a positive linear relationship between \(x\) and \(y\). When \(r < 0\), there is a negative linear relationship between \(x\) and \(y\). When \(r = 0\) or is approximately zero, there is no (or little) linear relationship between \(x\) and \(y\). The formula for the correlation coefficient is as follows:

   \[ r = \frac{1}{n-1}\cdot\frac{1}{S_x \cdot S_y}\cdot\sum_{i=1}^{n}(x_i - \bar{x})(y_i - \bar{y}) \]

   Where \(n\) is the number of data points, \(x_i\) and \(y_i\) are the \(i^\text{th}\) data points, \(\bar{x}\) and \(\bar{y}\) are the means of \(x\) and \(y\) respectively, and \(S_x\) and \(S_y\) are the sample standard deviations of \(x\) and \(y\) respectively. To compute the sample standard deviation of a set of values \(S\), we use the formula:

   \[ S_x = \sqrt{\frac{\sum_{i=1}^{|S|}(x_i - \bar{x})^2}{|S| - 1}} \]

   Design the double correlationCoefficient(double[] xs, double[] ys) method that, when given two arrays of doubles xs and ys, returns the correlation coefficient between the two arrays.

   Note: You may assume that \( |\mathit{xs}| = |\mathit{ys}| \) and that both arrays have at least two elements.

   Hint: The \(\sum\) notation may look intimidating, but it just means "the sum of."

   Files to Submit: Problem3.java, Problem3Test.java

4. (12 points) This problem has three parts.

   1. Design the standard recursive int findMaxWordLength(String[] S) method, which receives a String[] and returns the length of the longest word in the array.

      Note: Assume that the array contains at least one string.

      Hint: You should design a helper method to recurse over the array. The helper method must be standard recursive.

   2. Design the tail recursive int findMaxWordLengthTR(String[] S) method that uses tail recursion to solve the problem. You will need to design a helper method. Remember to include the relevant access modifiers!

   3. Design the int findMaxWordLengthLoop(String[] S) method that solves the problem using a loop.

   Files to Submit: Problem4.java, Problem4Test.java

5. (18 points) This problem has three parts.

   Consider the following data definition:

   A ValidPolynomial is one of:
    - Var
    - PositiveInteger
    - PositiveInteger Var "^" PositiveInteger
    - ValidPolynomial " + " ValidPolynomial
    - ValidPolynomial " - " ValidPolynomial
     

   Suppose we want to write the int evalPolynomial(String p, char v, int n) method that, when given a “valid polynomial”, a variable v, and a value n, evaluates the polynomial with respect to v at n. Design this method, but do so in a piecemeal fashion:

   1. Design the boolean isPositiveInteger(String s) method that returns whether s is a string that represents a positive integer. You may assume that the integer it returns is always within the bounds of a valid 32-bit integer.

      Warning: You are not allowed to use any built-in parsing methods such as Integer.parseInt, nor can you use exceptions to trivialize the problem. You must traverse over the string character by character.

   2. Design the String[] extract(String s) method that retrieves the components of a valid polynomial of the form ax^n, where a and n are positive integers, and x is a variable, but not necessarily the character 'x'.

      extract("5x^4")    => [5, 4]
      extract("9x^1")    => [9, 1] 
      extract("102x^10") => [102, 10]
            

   3. Finish the evalPolynomial method. You may assume that the given variable v is always the sole variable used in the given expression.

      evalPolynomial("3x^1 + 3", 'x', 3)                         => 12
      evalPolynomial("4x^4 + 7x^3 + 21x^2 - 65x^1 + 3", 'x', 0)  => 3
      evalPolynomial("4x^4 + 7x^3 + 21x^2 - 65x^1 + 3", 'x', 16) => 295155
            

   Files to Submit: Problem5.java, Problem5Test.java

6. (12 points) Design the int countAdjacentZeroSums(int[][] A) method that receives a two-dimensional array A and returns the number of row-adjacent cells that sum to zero. By row-adjacent, we mean two cells that are ordered one after the other in a row-major order traversal over the array. Consider the following \(4\times 3\) array. We see that A[0][0] and A[0][1] are side-by-side and sum to zero. Additionally, A[2][4] and A[3][0] are side-by-side when considering a row-major traversal and sum to zero. There are no other adjacent zero sums, so we return 2.

   \[ \begin{bmatrix} -5 & 5 & 1 & 3 & 0\\ 9 & 3 & 12 & -3 & 17\\ 23 & 31 & -42 & -8 & 16\\ -16 & -23 & 18 & -8 & -7 \end{bmatrix} \]

   Files to Submit: Problem6.java, Problem6Test.java

7. (14 points) One way to solve a system of equations is to put the values into a matrix and use “Gaussian elimination” to get a “triangular matrix.” If none of that makes sense, then consider an int[][] of the following:

   \[ \begin{bmatrix} 3 & 4 & -2 & 5\\ 0 & -6 & -7 & 1\\ 0 & 0 & 2 & -3 \end{bmatrix} \]

   Notice that the bottom-left “corner” of the matrix is all zeroes. To be more formal, for every row \(i\), the first \(i-1\) elements are zero. It looks like a triangle of zeroes, hence the “triangular matrix” label. Note that the matrix represents the following system of equations:

   \[ \begin{aligned} 3x + 4y - 2z &= 5\\ -6y - 7z &= 1\\ 2z &= -3 \end{aligned} \]

   We can very easily figure out the value of \(z\): divide both sides of the equation by \(2\) to deduce that \(z=-1.5\). From there, we plug in \(-1.5\) into \(-6y - 7z = 1\) to get \(-6y - 11.5 = 1\) and, to solve for \(y\), subtract \(-11.5\) from both sides to get \(-6y = 12.5\), then \(y=-6.25\). Finally, plug \(z=-1.5\) and \(y=6.25\) into \(3x+4y-2z=5\) to get \(3x + 25 + 3 = 5\). To solve for \(x\), subtract \(25\) and \(3\) from \(5\) to get \(3x=-23\). Dividing both sides by \(3\) gets us \(x\approx -7.66\).

   Design the double[] solveTriangularMatrix(int[][] M) that returns an array of the solutions to the system of equations defined by M. The indices of the returned array correspond to the variables of the equation. You may assume that index 0 is the first variable, index 1 is the second variable, and so forth. Assume that the input matrix is always a valid triangular matrix representing a system of equations with a unique solution.

   Hint 1: Start from the last row and work your way up to the top.

   Hint 2: This technique of computing variables and working upwards is called back substitution.

   Files to Submit: Problem7.java, Problem7Test.java

8. (12 points) The Kronecker product of two 2-D arrays \(A = P \times Q\) (with \(P\) rows and \(Q\) columns), and \(B = R \times S\) (with \(R\) rows and \(S\) columns) is defined as follows: for every element \(a \in A\), multiply it with the entirety of \(B\). This produces a new matrix of size \(PR \times QS\). For example, take the following two matrices:

   \[ \begin{aligned} A &= \begin{bmatrix} 1 & 2 & 5\\ 3 & -4 & -7 \end{bmatrix} \qquad B = \begin{bmatrix} 5 & 0\\ 6 & 7\\ -3 & 0\\ \end{bmatrix} \end{aligned} \]

   The Kronecker product of \(A\) and \(B\), denoted \(A \otimes B\), is:

   \[ A \otimes B = \begin{bmatrix} (1\cdot B) & (2\cdot B) & (5\cdot B)\\ (3\cdot B) & (-4\cdot B) & (-7\cdot B) \end{bmatrix} = \begin{bmatrix} 5 & 0 & 10 & 0 & 25 & 0\\ 6 & 7 & 12 & 14 & 30 & 35\\ -3 & 0 & -6 & 0 & -15 & 0\\ 15 & 0 & -20 & 0 & -35 & 0\\ 18 & 21 & -24 & -28 & -42 & -49\\ -9 & 0 & 12 & 0 & 21 & 0 \end{bmatrix} \]

   1. Design the int[][] constantMultiply(int n, int[][] M) method that, when given an integer \(n\) and a two-dimensional array M, returns a new array where each element of M is multiplied by \(n\).

   2. Design the int[][] kroneckerProduct(int[][] A, int[][] B) method that, when given two two-dimensional arrays A and B, returns their Kronecker product. Assume that both arrays are at least \(1 \times 1\) in size.

   Files to Submit: Problem8.java, Problem8Test.java