CSE 331: Section 09 - Finals Review (Solutions)

Task 1 - Generics/Subtyping

Suppose that we have the following classes:

class Food {..}
class Breakfast extends Food {..}
class Snacks extends Food {..}
class BeansOnToast extends Breakfast {..}
class Congee extends Breakfast {..}
class MiniPizza extends Snacks {..}

and the following variables:

Object obj;
Food food;                        List<Food> foods;
Breakfast breakfast;              List<? extends Breakfast> breakfasts;
Snacks snacks;                    List<Snacks> snackFoods;
BeansOnToast beansOnToast;        List<? super BeansOnToast> beanFoods;
Congee congee;                    List<Congee> congees;
MiniPizza miniPizza;              List<MiniPizza> miniPizzas;

For each line of code below, state whether the call is legal or illegal. If it is illegal, briefly explain why.

foods.add(congee);

This is legal since Congee is a subclass of Food, so it can be added to a List<Food>.
breakfasts.add(congee);

This is illegal since breakfasts is a List<? extends Breakfast>, and elements cannot be added because the exact subtype of Breakfast is unknown.
beanFoods.add(beansOnToast);

This is legal since beanFoods is a List<? super BeansOnToast> and accepts BeansOnToast or its subclasses.
beanFoods.add(breakfast);

This is illegal since Breakfast is not guaranteed to be a subtype of BeansOnToast.
snackFoods.add(miniPizza);

This is legal since snackFoods is a List<Snacks> and MiniPizza is a subclass of Snacks.
food = congees.get(0);

This is legal since Congee is a subtype of Food.
breakfast = breakfasts.get(0);

This is legal since ? extends Breakfast guarantees that returned values are assignable to Breakfast.
miniPizza = foods.get(0);

This is illegal since foods may contain any subtype of Food, not necessarily a MiniPizza.
obj = beanFoods.get(0);

This is legal since any object retrieved from a generic collection is assignable to Object.
congee = breakfasts.get(0);

This is illegal since breakfasts could contain any subtype of Breakfast, not necessarily Congee.

ADT

Tasks 2-5 refer to the following generic MutableTreeSet ADT.

/**
 * Represents a **mutable** set of distinct, non-null values logically stored in a 
 * binary search tree. 
 */
public interface MutableTreeSet<T extends Comparable<T>> {

  /**
   * Determines whether value is in the set.
   * @param value the value to look for in the set
   * @return true if value is in the set, false otherwise
   */
  public boolean contains(T value);

  /**
   * Adds value to the set if not already present.
   * @param value the non-null value to add to the set
   * @modifies this
   * @effects this is unchanged if this_0 contains value
   *          otherwise, this contains all of this_0 and value
   */
  public void add(T value);

  /**
   * Removes the minimum value from the TreeSet as defined by the compareTo()
   * method of type T
   * @requires set is not empty
   */
  public void removeMin();

  /**
   * Returns the set as a sorted list. Only call for testing purposes;
   * @return the set as a sorted list.
   */
  public List<T> getSetAsListForTestingDoNotCallOrElse();
}

Task 2 - AF/RI

A TreeSet is a Java Collection that holds unique elements in a sorted order. The official TreeSet manages this with a Red-Black Tree, a self-balancing variant of a Binary Search Tree, but our MutableTreeSetImpl<T extends Comparable<T>> will use a simple BST of the following Node instead.

private class Node {
  public final T data;
  public Node left;
  public Node right;

  public Node(T data) {
    this(data, null, null);
  }

  public Node(T data, Node left, Node right) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

Write the AF and RI for our MutableTreeSetImpl. We've started it below* (some bullet points may go unused). (Hint: How do you find the sorted order of a BST? What properties are required by a BST?).

*The second and third bullet points say the nodes form a valid binary tree.

public class MutableTreeSetImpl<T extends Comparable<T>> {
  private Node overallRoot;
  /**
  * AF(this) = 
  *
  * RI:
  * - No duplicate values exist in the tree.
  * - The graph of nodes contains no cycles.
  * - No two nodes point to the same child node.
  * -
  * -
  * -
  * -
  */
  ...
}

/**
 * AF(this) = the values obtained from an in-order traversal of the
 *            tree rooted at overallRoot
 *
 * RI:
 * - No duplicate values exist in the tree.
 * - The graph of nodes contains no cycles.
 * - No two nodes point to the same child node.
 * - For every node, every value in the left subtree is less
 *   than the node's value.
 * - For every node, every value in the right subtree is greater
 *   than the node's value.
 * - No node contains a null value.
 */

Task 3 - Coding

In this problem, you will implement a few methods regarding MutableTreeSet.

With the given loop invariant below, fill in the missing parts of the code to make it correct.

/**
 * Creates a new MutableTreeSet containing all distinct elements from
 * the given array.
 * @param values the array of elements to build the new set from
 * @requires values != null and values does not contain any null elements
 * @return a new MutableTreeSet containing all distinct elements from values
 */
public static <T extends Comparable<T>> MutableTreeSet<T> 
    buildSetFromArray(T[] values) {
  MutableTreeSet<T> ans = new MutableTreeSetImpl<>();
  int i = ____________________;

  // Inv: ans contains all distinct elements from values[0 : i]
  while (________________________________________) {







  }
  return ans;
}

public static <T extends Comparable<T>> MutableTreeSet<T> 
    buildSetFromArray(T[] values) {
  MutableTreeSet<T> ans = new MutableTreeSetImpl<>();
  int i = 0;

  // Inv: ans contains all distinct elements from values[0 : i]
  while (i != values.length) {
    ans.add(values[i]);
    i++;
  }
  return ans;
}

Now, implement add() to adhere to the RI that you wrote in Task 2. Make sure to adhere to the CSE 331 Code Quality guidelines. You may assume a checkRep() is correctly implemented.

/**
 * Adds value to the set if not already present.
 * @param value the value to add to the set
 * @requires value != null
 * @modifies this
 * @effects this is unchanged if this_0 contains value
 * otherwise, this contains all of this_0 and value
 */
public void add(T value) {















}

public void add(T value) {
  if (value == null) {
    throw new IllegalArgumentException("value cannot be null");
  }

  checkRep();
  overallRoot = add(overallRoot, value);
  checkRep();
}

private Node add(Node root, T value) {
  if (root == null) {
    return new Node(value);
  }

  int cmp = value.compareTo(root.data);
  if (cmp < 0) {
    root.left = add(root.left, value);
  } else if (cmp > 0) {
    root.right = add(root.right, value);
  }

  return root;
}

Task 4 - MutableTreeSetImpl Floyd Reasoning

For the following 2 tasks, please refer to next block of code below:

  private Node overallRoot;

  /**
   * Removes the minimum value from the TreeSet as defined by the compareTo()
   * method of type T
   * @requires set is not empty
   * @modifies this
   * @effects this = this without its minimum value 
   */
  public void removeMin() {
    checkRep();
    {{I1: _______________________________________}}
    overallRoot = removeMin(overallRoot);
    {{P1: _______________________________________
      ___________________________________________}}
    checkRep();
  }

  /**
   * Removes the minimum element from the subtree at root and returns
   * the updated subtree
   * @param root the root node of the subtree to remove the node from
   * @requires root is a valid BST
   * @requires root is not null
   * @return the root node of the new BST subtree which is the original
   * subtree with the minimum value node removed. The returned subtree
   * is a valid BST.
   */
  private Node removeMin(Node root) {
    {{________________________________________________}}
    if (root.left != null) {
      {{I2: __________________________________________}}
      root.left = removeMin(root.left);
      {{P2: __________________________________________
        ______________________________________________}}
      return root;
    }
    {{P3: ____________________________________________}}
    return root.right;
  }

Use forward reasoning to fill in the assertions for P1, P2, and P3.

  private Node overallRoot;

  /**
   * Removes the minimum value from the TreeSet as defined by the compareTo()
   * method of type T
   * @requires this is not empty
   * @modifies this
   * @effects this = this without its minimum value
   */
  public void removeMin() {
    checkRep();
    {{I1: AF(this) is not empty and RIs}}
    overallRoot = removeMin(overallRoot);
    {{P1: overallRoot = the root node of the new BST subtree which is
          the original subtree with the minimum value node removed and
          overallRoot is the root of a valid BST}}
    checkRep();
  }

  /**
   * Removes the minimum element from the subtree at root and returns
   * the updated subtree
   * @param root the root node of the subtree to remove the node from
   * @requires root is a valid BST
   * @requires root is not null
   * @return the root node of the new BST subtree which is the original
   * subtree with the minimum value node removed. The returned subtree
   * is a valid BST.
   */
  private Node removeMin(Node root) {
    {{root is a valid BST and root is not null}}
    if (root.left != null) {
      {{I2: root is a valid BST and root is not null and root.left != null}}
      root.left = removeMin(root.left);
      {{P2: root is a valid BST and root is not null and root.left_0
        != null and root.left = the root node of the new BST subtree
        which is the original subtree with the minimum value node
        removed and root.left is the root of a valid BST}}
      return root;
    }
    {{P3: root is a valid BST and root is not null and root.left = null}}
    return root.right;
  }

Explain why I1 implies the precondition of removeMin(Node root):

The precondition is that the argument is not null and is a valid BST.

I1 says that AF(this) is not empty, which means there is at least one node. This means the root cannot be null.

I1 also says the RIs hold, which include the fact that the root is a valid BST.
Explain why P1 implies the postcondition of removeMin():

Since we know that "overallRoot = the root node of the new BST subtree which is the original subtree with the minimum value node removed", and we know that this equals the values obtained from an in-order traversal of the tree rooted at overallRoot, we essentially know that this = this_0 without the minimum value.

Additionally, we know that the returned tree is also a valid BST which means it satisfies all representation invariants.
Explain why I2 implies the precondition of removeMin(Node root):

Since we know that root is a valid BST and therefore meets all RIs, we also know that root.left is also a valid BST as all of the RIs apply to every node in the tree. Additionally, we know directly that root.left != null.
Explain why P2 implies the postcondition of removeMin(Node root):

Since root is a valid BST, we know it must satisfy all RIs in the ADT. Additionally, since we know that root.left_0 != null, we know from the RIs that all values contained the left subtree are less than root's value, we know that the minimum value must be in the left subtree of root. Since at the end, root.left is the original left subtree without minimum value, we know that root is now a new subtree that is the same as the original subtree without the minimum value.

Lastly, since we know that the tree rooted at root.left is still a valid BST, we know that the tree rooted at root is also still a valid BST.
Explain why P3 implies the postcondition of removeMin(Node root):

root is a valid BST and root is not null and root.left = null value returned root.right

Since root is a valid BST, we know it must satisfy all RIs in the ADT. Additionally, since we know that root.left = null, we know from the RIs that root must contain the minimum value in the subtree since any smaller values would be contained in the left subtree. Therefore, we must return the subtree without root which is root.right since the left subtree is empty and contains no values.

Lastly, since we know that the tree rooted at root is a valid BST, we know that the tree rooted at root.right is also still a valid BST so the returned value is a valid bst.

Task 5 - Testing

Write spec tests that fully satisfy our testing heuristics for the removeMin() implementation. You may assume that the MutableTreeSetImpl class if a fully functional implementation that contains the removeMin() implementation from Task 4.

*Note that you should not call the private removeMin(Node root) method directly in your testing code.

@Test
public void testRemoveMin() {














}

@Test
public void testRemoveMin() {
  // Test 0 recursive calls and false branch coverage
  MutableTreeSet<Integer> set = new MutableTreeSetImpl<>();
  set.add(1);
  set.removeMin();
  assertEquals(List.of(), set.getSetAsListForTestingDoNotCallOrElse());

  // Test 1 recursive call and true branch coverage
  set.add(1);
  set.add(0);
  set.removeMin();
  assertEquals(List.of(1), set.getSetAsListForTestingDoNotCallOrElse());


  // Test 2+ recursive call and true branch coverage
  set.add(0);
  set.add(-1);
  set.removeMin();
  assertEquals(List.of(0, 1), set.getSetAsListForTestingDoNotCallOrElse());

  // Full statement coverage is achieved by the above tests
}

Task 6 - Client/server webdev Short Answer

In client/server programming, if the client state and the server state disagree with each other, which one is considered "right"?

The server's state is the source of truth.
If you receive a 500 status code after sending a request to a server. What is the most likely source?

A 500 error indicates the server crashed or had another kind of error that was not the client's fault. Check the server logs for an error trace.
Why do servers generally need to run all of the time (24/7) whereas clients do not?

Servers are generally passive and as such they don't know when a client request might come. As a result, they must always be listening for client requests so that they can serve them. Clients on the other hand are the ones reaching out so they can run only when they are needed to a specific task and then turned off when they are no longer needed.

Task 7 - Design pattern Short Answer

Name a problem with Java constructors and a design pattern that helps work around that problem.
There are many correct answers:
- Constructors don't have names. Static factory methods do.
- Constructors cannot change their mind about what type of object to construct. Factories can.
- Constructors cannot decide not to allocate an object. Singleton/interning via factories do this.
Why are method calls from constructors often dangerous?

The representation invariant is often not established until the constructor finishes, so methods may run while the object is in an inconsistent state.
Why is preventing a bug by design preferable to testing for it?

If a bug is impossible by design, no testing or reasoning is needed to show that the bug cannot occur.

Task 8 - Software Design Short Answer

Is it better to tightly- or loosely-couple your client to an implementation?

It's better to loosely-couple. It allows the implementation to change without breaking the client, as long as the new implementation still satisfies the specification.
If you have full testing coverage and pass all tests, can you be confident that your program is correct?

No! You can only be confident that it works on the specific inputs that were tested. You can only be confident in correctness if you reason through the code and prove it correct on all allowed inputs!
Why is it important to write a good specification?

Clear specs eliminate ambiguity. When multiple programmers are working together, a good specification of the interface between them allows them to work independently with confidence.
When and why do we make defensive checks? When and why do we check our Rep Invariant?

We make defensive checks when it's cheap to do so, meaning it doesn't increase the time complexity of a method. We do this because even if we clearly restrict preconditions in a spec, programmers often skip reading these specs and call the method illegally anyway. Failing early makes debugging much easier.

We check our Representation Invariant (via a checkRep() method) at the end of constructors, at the beginning and end of mutators, and at the beginning of observers. We do this to catch representation exposure (e.g., if a client modifies a mutable field they gained access to) and to ensure our own methods don't accidentally leave the object in an invalid state. Like other defensive checks, we usually only run the "fast" parts of the RI check in production to avoid degrading performance.