CSE 331: Section 10 — Finals Revew

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);
breakfasts.add(congee);
beanFoods.add(beansOnToast);
beanFoods.add(breakfast);
snackFoods.add(miniPizza);
food = congees.get(0);
breakfast = breakfasts.get(0);
miniPizza = foods.get(0);
obj = beanFoods.get(0);
congee = breakfasts.get(0);

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.
  * -
  * -
  * -
  * -
  */
  ...
}

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;
}

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) {















}

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 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.
Prove I1 implies the precondition of removeMin(Node root):
Prove P1 implies the postcondition of removeMin():
Prove I2 implies the precondition of removeMin(Node root):
Prove P2 implies the postcondition of removeMin(Node root):
Prove P3 implies the postcondition of removeMin(Node root):

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() {














}
```

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?
If you receive a 404 status code after sending a request to a server. What is the most likely source?
Why do servers generally need to run all of the time (24/7) whereas clients do not?

Task 7 - Design pattern Short Answer

What problem does the Iterator pattern solve?
What does it mean to make a bug impossible by design?
Why are method calls from constructors often dangerous?
Why is preventing a bug by design preferable to testing for it?

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?
If you have full testing coverage and pass all tests, can you be confident that your program is correct?
Why is it important to write a good specification?
When and why do we make defensive checks? When and why do we check our Rep Invariant?