CSE 331: Section 10 - 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 obj
   * @effects obj is unchanged if obj_0 contains value
   *          otherwise, obj contains all of obj_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: obj = 
  *
  * 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:
 * obj = 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 obj
 * @effects obj is unchanged if obj_0 contains value
 * otherwise, obj contains all of obj_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

  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 obj
   * @effects obj = obj 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
   */
  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 set is not empty
   * @modifies obj
   * @effects obj = obj without its minimum value
   */
  public void removeMin() {
    checkRep();
    {{I1: set 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
   */
  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;
  }

Prove I1 implies the precondition of removeMin(Node root):

Since we know that the set is not empty and obj = the values obtained from an in-order traversal of the tree rooted at overallRoot, we know that overallRoot != null.

Since we know all RIs are true, they imply that the tree rooted at overallRoot is a valid BST. Therefore, the precondition of removeMin(Node root) holds.

Prove 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 obj = the values obtained from an in-order traversal of the tree rooted at overallRoot, we essentially know that obj = obj\(_0\) without the minimum value.

Additionally, we know that the returned tree is also a valid BST which means it satisfies all representation invariants.

Therefore, the postcondition holds.

Prove 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.

Therefore, the precondition of removeMin(Node root) holds.

Prove 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.

Therefore, the postcondition holds.

Prove 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.

Therefore, the postcondition holds.

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, which side stores the majority of the state? How do they share that state with the other side? How might the other side modify the stored state?

In client/server programming, the server stores the majority of the state. It typically shares the state to the client through a response to a client request, either by sending back HTML code for the client's browser to render or more commonly nowadays through a JSON object that the client's browser can render. The client can modify the server's state by sending requests to the server.

If you receive a 404 status code after sending a request to a server. What is the most likely source?

A 404 error indicates a not found error. This likely means that the endpoint or URL that we sent the request to doesn't actually exist.

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

What problem does the Iterator pattern solve?

It allows clients to traverse a collection without exposing the collection's internal representation.

What does it mean to make a bug impossible by design?

It means designing the API, representation, or type system so that certain incorrect programs cannot be written or compiled.

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 - AI-Assisted Programming Short Answer

Is it better to tightly- or loosely-couple your client to an implementation? Which one does AI tend to do?

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. AI tends to cross this abstraction barrier, tightly coupling your client to a specific implementation, which causes unexpected bugs as you rely on things that are not guaranteed to be true!

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 prompting AI, a formal specification restricts the AI's output to a well-defined contract, preventing it from making incorrect assumptions about edge cases or mutability.

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.