Problems

1. (20 points) Repeated string concatenation is a common performance issue in Java. As we know, Java String objects are immutable, which means that concatenation creates new String objects. This is fine for small strings, but for larger strings (or concatenation operations performed in a loop), this can be a performance bottleneck. Each concatenation requires copying the entire string. Java provides the StringBuilder class to alleviate the issue. In this exercise, you will design a MiniStringBuilder class that mimics the behavior of StringBuilder. You cannot use StringBuilder or the older StringBuffer classes in your implementation.

   1. Design the MiniStringBuilder class, which stores a char[] as an instance variable. The class should also store a variable to keep track of the number of "logical characters" that are in-use by the buffer.

   2. Design two constructors for the MiniStringBuilder class: one that receives no arguments and initializes the default capacity of the underlying char[] array to 20, and another that receives a String s and initializes the char[] array to the characters of s.

   3. Override the equals method to return whether two MiniStringBuilder objects represent the same string.

   4. Override the hashCode method to return the hash code of the MiniStringBuilder object. The hash code is defined as the hash code of the underlying array of characters. Use Arrays.hashCode rather than Objects.hash.

   5. Override the toString method, which returns the char[] array as a String object. The resulting string should contain only the logical characters in the buffer, and not the entire array. Output the characters without any additional characters, such as brackets or commas.

   6. Design the void append(String s) method, which appends the given string s onto the end of the current string stored in the buffer. The given string should not simply be appended onto the end of the buffer, but rather added to the end of the previous string in the buffer. If the buffer runs out of space, reallocate the array to be twice its current size, similar to how we reallocate the array in the MiniArrayList example class.

   7. Design the void clear() method, which resets the char[] array to the default size of 20 and clears the character buffer.

   Files to Submit: MiniStringBuilder.java, MiniStringBuilderTest.java

2. (20 points) This question has seven parts.

   1. Design the Matrix class, which stores a two-dimensional array of integers. Its constructor should receive two integers m and n representing the number of rows and columns respectively, as well as a two-dimensional array of integers (you may assume that the number of rows and columns of the passed array are equal to m and n). Copy the integers from the passed array into an instance variable array.

      Warning: Do not simply assign the provided array to the instance variable!

   2. Design the int[][] getMatrix() method, which returns a copy of the underlying two-dimensional array of integers.

   3. Design the boolean set(int i, int j, int val) method, which sets the value at row i and column j to val. If the row or column is out of bounds, return false and do not set the value. Otherwise, set the value and return true.

   4. Design the boolean add(Matrix m) method, which adds the values of the passed matrix to the current matrix. If the dimensions of the passed matrix do not match the dimensions of the current matrix, return false and do not add the matrix.

   5. Design the boolean multiply(Matrix m) method, which multiplies the values of the passed matrix to the current matrix. Two matrices \(A=P\times Q\), \(B=R\times S\) can be multiplied if and only if \(Q = R\). The resulting matrix has dimensions \(P \times S\). Therefore, we need a case analysis: if we cannot multiply \(m\) with this matrix, return false and do not multiply the matrix. The product of two matrices \(A\) and \(B\) is the matrix \(C\) where \(C_{i, j} = \sum_{k=1}^{N} A_{i, k}\cdot B_{k, j}\) for the indices \(i\), \(k\), and \(j\).

      Hint 1: Use three for loops!

      Hint 2: This problem makes use of a variable \(N\) that is not explicitly given in the problem. What does \(N\) represent? Think about it...

   6. Design the void transpose() method, which transposes the matrix. That is, the rows become the columns and the columns become the rows. You may need to alter the dimensions of the matrix.

   7. Design the void rotate() method, rotates the matrix 90 degrees clockwise. To rotate a matrix, compute the transposition and then reverse the rows. You may need to alter the dimensions of the matrix.

   8. Override the toString method to return a stringified version of the matrix. As an example, "[[1, 2, 3], [4, 5, 6]]" represents the following matrix:

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

   Files to Submit: Matrix.java, MatrixTest.java

3. (20 points) A complex number \(c \in \mathbb{C}\) has two components: a real part \(\text{Re}(c) \in \mathbb{R}\) and an imaginary part \(\text{Im}(c) \in \mathbb{R}\). Together, these components compose into \(a + bi\). In this problem, you will design a class that represents complex numbers whose components are int values, to simplify the problem.

   For a bit of motivation behind why complex numbers are interesting, see the Mandelbrot fractal.

   1. Design the ComplexNumber class, whose constructor receives two int values: \(a\) and \(b\). Store these as the real and imaginary parts of the complex number, respectively.

   2. Design the empty constructor that initializes \(a\) and \(b\) to 0.

   3. Design the int getReal() and int getImaginary() accessor methods to return the respective instance variables.

   4. Override the equals method to return whether two ComplexNumber objects are equal. Two ComplexNumber objects are equal if and only if their constituents are equal.

   5. Design the hashCode method to return the hash code of this ComplexNumber object. Its hash code is defined as invoking Objects.hash on the real and imaginary components.

   6. Override the toString method to return a string representation of the complex number of the form "a + bi", "a - bi", or "a" when b is either positive, negative, or 0 respectively.

   7. Design the double magnitude() method, which returns the magnitude of this ComplexNumber. The magnitude of a complex number is defined as the square root of the sums of the squares of its components: \(\sqrt{a^2 + b^2}\).

   8. Design the Optional<Double> argument() method, which returns the argument, or angle, of this ComplexNumber in radians. The argument of a complex number is computed by \(\tan^{-1}(b/a)\). If the real component is zero, then the argument is undefined; return an empty Optional.

      Warning: Don't forget about integer division!

   9. Design the ComplexNumber conjugate() method, which returns the conjugate of this complex number. The conjugate of a complex number flips the parity of the imaginary component. That is, if we have a complex number a + bi, its conjugate is a - bi.

   10. Design the ComplexNumber add(ComplexNumber c2) method, which receives a ComplexNumber as an argument and returns a new ComplexNumber representing the sum of this complex number and the given number. The sum of two complex numbers is the sum of the real components and the imaginary components.

   11. Design the ComplexNumber sub(ComplexNumber c2) method, which receives a ComplexNumber as an argument and returns a new ComplexNumber representing the difference of this complex number and the given number. The difference of two complex numbers is the difference of the real components and the imaginary components.

   12. Design the ComplexNumber mul(ComplexNumber c2) method, which receives a ComplexNumber as an argument and returns a new ComplexNumber representing the product of this complex number and the given number. The product of two complex numbers is as follows:

       \[ (a + bi)(c + di) = (ac - bd) + (ad + bc)i \]

   Files to Submit: ComplexNumber.java, ComplexNumberTest.java

4. (40 points) A persistent data structure is one that saves intermittent data structures after applying operations that would otherwise alter the contents of the data structure. Take, for instance, a standard FIFO queue. When we invoke its enqueue/add method, we mutate the underlying data structure to now contain the new element. If this were a persistent queue, then enqueueing a new element would, instead, return a new queue that contains all elements and the newly-enqueued value, thereby leaving the original queue unchanged.

   1. First, design the generic, private, and static class Node inside a generic PQueue class skeleton. It should store, as instance variables, a pointer to its next element as well as its associated value.

   2. Then, design the PQueue class, which represents a persistent queue data structure. As instance variables, store "first" and "last" pointers as Node objects, as well as an integer to represent the number of existing elements. In the constructor, instantiate the pointers to null and the number of elements to zero.

   3. Design the private PQueue<T> copy() method, which returns a new queue with the same elements as the current queue.

      Hint: You should divide this method into a case analysis: one where this queue is empty and another where it is not. In the former case, return a new queue with no elements. In the latter case, iterate over the elements of the queue, enqueuing each element into a new queue. You will need to instantiate a new Node (reference) for each element.

   4. Override the equals method to return whether the elements of this queue are equal to the provided queue's elements. You will need to traverse over the queues in a fashion similar to how you do it in copy.

      Hint: Again, break this up into a case analysis: (1) if the provided object is not a PQueue<?>, return false. (2) Otherwise, if they do not have the same number of elements, return false. Otherwise, compare each element sequentially.

   5. Design the PQueue<T> enqueue(T t) method, which enqueues a value onto the end of a new queue containing all the old elements, in addition to the new value. You should use the copy method to your advantage.

   6. Design the PQueue<T> dequeue() method, which removes the first element of the queue, returning a new queue without this first value. You should use the copy method to your advantage.

   7. Design the T peek() method, which returns the first element of the queue, or null if the queue is empty.

   8. Design the static <T> PQueue<T> of(T... vals) method, which creates a queue with the values passed as vals. Note that this must be a variadic method.

      Warning: Do not create a series of PQueue objects by enqueueing each element into a distinct queue; this is incredibly inefficient. Instead, allocate each Node one-by-one, thereby never calling enqueue.

   9. Design the int size() method, which returns the number of elements in the queue. You should not traverse the queue to compute this value.

   Files to Submit: PQueue.java, PQueueTest.java