CSE 331�Software Design & Implementation
Summer 2026
Section 9 – Final Review
Administrivia
Final
Course Evals!!
DO YOUR EVALS!!!!
DO IT!!
List of Topics
* Likely Short Answer/MCQ/Mutltiselect
Vote which 2-3 tasks to review!
* Bold are new topics after the midterm
Task 1 - Generics/Subtype
class Food {..}
class Breakfast extends Food {..}
class Snacks extends Food {..}
class BeansOnToast extends Breakfast {..}
class Congee extends Breakfast {..}
class MiniPizza extends Snacks {..}
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;
a. foods.add(congee);
This is legal since Congee is a subclass of Food, so it can be added to a List<Food>.
b. 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.
c. beanFoods.add(beansOnToast);
This is legal since beanFoods is a List<? super BeansOnToast> and accepts BeansOnToast or its subclasses.
d. beanFoods.add(breakfast);
This is illegal since Breakfast is not guaranteed to be a subtype of BeansOnToast.
e. snackFoods.add(miniPizza);
This is legal since snackFoods is a List<Snacks> and MiniPizza is a subclass of Snacks.
Task 1 - Generics/Subtype
class Food {..}
class Breakfast extends Food {..}
class Snacks extends Food {..}
class BeansOnToast extends Breakfast {..}
class Congee extends Breakfast {..}
class MiniPizza extends Snacks {..}
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;
f. food = congees.get(0);
This is legal since Congee is a subtype of Food.
g. breakfast = breakfasts.get(0);
This is legal since ? extends Breakfast guarantees that returned values are assignable to Breakfast.
h. miniPizza = foods.get(0);
This is illegal since foods may contain any subtype of Food, not necessarily a MiniPizza.
i. obj = beanFoods.get(0);
This is legal since any object retrieved from a generic collection is assignable to Object.
j. congee = breakfasts.get(0);
This is illegal since breakfasts could contain any subtype of Breakfast, not necessarily Congee.
Task 2 - AF/RI
MutableTreeSetImpl<T extends Comparable<T>> will use a simple BST of the following Node
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.
(Hint: How do you find the sorted order of a BST? What properties are required by a BST?).
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.
* -
* -
* -
* -
*/
...
}
Task 2 - AF/RI
MutableTreeSetImpl<T extends Comparable<T>> will use a simple BST of the following Node
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.
(Hint: How do you find the sorted order of a BST? What properties are required by a BST?).
public class MutableTreeSetImpl<T extends Comparable<T>> {
private Node overallRoot;
/**
* 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.
* -
* -
* -
* -
*/
...
}
Task 2 - AF/RI
MutableTreeSetImpl<T extends Comparable<T>> will use a simple BST of the following Node
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.
(Hint: How do you find the sorted order of a BST? What properties are required by a BST?).
public class MutableTreeSetImpl<T extends Comparable<T>> {
private Node overallRoot;
/**
* 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.
* -
* -
*/
...
}
Task 2 - AF/RI
MutableTreeSetImpl<T extends Comparable<T>> will use a simple BST of the following Node
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.
(Hint: How do you find the sorted order of a BST? What properties are required by a BST?).
public class MutableTreeSetImpl<T extends Comparable<T>> {
private Node overallRoot;
/**
* 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.
* -
*/
...
}
Task 2 - AF/RI
MutableTreeSetImpl<T extends Comparable<T>> will use a simple BST of the following Node
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.
(Hint: How do you find the sorted order of a BST? What properties are required by a BST?).
public class MutableTreeSetImpl<T extends Comparable<T>> {
private Node overallRoot;
/**
* 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 3a - Coding
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;
}
Task 3a - Coding
/**
* 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 = 0;
// Inv: ans contains all distinct elements from values[0 : i]
while (i != values.length) {
ans.add(values[i]);
i++;
}
return ans;
}
Task 3b - Coding
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) {
}
Task 3b - Coding
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;
}
* Note that you don’t call checkRep() inside a helper method - the RI is not guaranteed to hold at that point.
Task 4a - MutableTreeSetImpl Floyd Reasoning
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 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
*/
private Node removeMin(Node root) {
{{________________________________________________}}
if (root.left != null) {
{{I2: __________________________________________}}
root.left = removeMin(root.left);
{{P2: __________________________________________}}
return root;
}
{{P3: ____________________________________________}}
return root.right;
}
Task 4a - MutableTreeSetImpl Floyd Reasoning
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 this
* @effects this = this 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) {
{{________________________________________________}}
if (root.left != null) {
{{I2: __________________________________________}}
root.left = removeMin(root.left);
{{P2: __________________________________________}}
return root;
}
{{P3: ____________________________________________}}
return root.right;
}
Task 4a - MutableTreeSetImpl Floyd Reasoning
/**
* 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: ____________________________________________ }}
return root.right;
}
Task 4a - MutableTreeSetImpl Floyd Reasoning
/**
* 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;
}
Task 4b - MutableTreeSetImpl Floyd Reasoning
Prove I1 implies the precondition of removeMin(Node root):
{{I1: set is not empty and RIs}}
* @requires root is a valid BST
* @requires root is not null
Since we know that the set is not empty and this = 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.
Task 4c - MutableTreeSetImpl Floyd Reasoning
Prove P1 implies the postcondition of removeMin():
{{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}}
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 = the values obtained from an in-order traversal of the tree rooted at overallRoot, we essentially know that this = this0 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.
Task 4d - MutableTreeSetImpl Floyd Reasoning
Prove I2 implies the precondition of removeMin(Node root):
{{I2: root is a valid BST and root is not null and root.left != null}}
* @requires root is a valid BST
* @requires root is not null
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.
Task 4e - MutableTreeSetImpl Floyd Reasoning
Prove P2 implies the postcondition of removeMin(Node root):
{{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 the root node of the new BST subtree which is the
* original subtree with the minimum value node removed
Since root is a valid BST, we know it must satisfy all RIs in the ADT. Additionally, since we know that root.left0
!= 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.
Task 4f - MutableTreeSetImpl Floyd Reasoning
Prove P3 implies the postcondition of removeMin(Node root):
{{P3: root is a valid BST and root is not null and root.left = null}}
* @return the root node of the new BST subtree which is the
* original subtree with the minimum value node removed
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() {
}
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 0 recursive calls and false branch coverage
MutableTreeSet<Integer> set = new MutableTreeSetImpl<>();
set.add(1);
set.removeMin();
assertEquals(List.of(), set.getSetAsListForTestingDoNotCallOrElse());
}
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 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());
}
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 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());
}
Task 6 - Client/Server Webdev Short Answer
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.
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.
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
There are many correct answers:
b. 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.
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
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.
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!
Task 8 - Software Design Short Answer
c. 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.
d. 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.