CSE 12 Spring 2024 PA8 - BST and Sorting

Due date: Tuesday, June 4th @ 11:59 PM PT

There is an FAQ post on Piazza. Please read that post first if you have any questions.

Learning goals:

• Implement a Binary Search Tree
• Write JUnit tests to verify proper implementation
• Compare the efficiency of different sorting algorithms

Overview:

There are 2 parts to this assignment. All are required before the deadline and should be submitted on Gradescope:

• Part 1: Binary Search Tree [90 Points]
  • MyBST Implementation [75 Points]
  • Testing [10 Points]
  • Coding Style [5 Points]
• Part 2: Sort Detective [10 Points]

Part 1: Testing and Implementation of Binary Search Tree [90 points]

In this part of the assignment, you will implement a Binary Search Tree and write JUnit tests to ensure that your implementation functions correctly.

Make sure to read the entire write-up and also the starter code (including the comments) before you start coding. You may not change any public class/method or variable names given in the write-up or starter code.

Download the starter code and put it in a directory in your working environment. You will find the following files:

| +-- MyBST.java          Edit this file				
| +-- CustomTester.java   Create this file
| +-- PublicTester.java

Part 1A: MyBSTNode

This class is a static nested class of the MyBST class. Objects of this class represent the nodes of the binary search tree and contain the following private instance variables:

Instance Variable	Description
K key	The key that we are using to sort our nodes This key cannot be null Duplicate keys are not supported (duplicates are defined by compareTo() returning that the keys are equal)
V value	The data stored in this MyBSTNode This value can be null
MyBSTNode parent	A reference to the parent of this MyBSTNode If this node has no parent, then this will be null
MyBSTNode left	A reference to the left child of this MyBSTNode If this node has no left child, then this will be null
MyBSTNode right	A reference to the right child of this MyBSTNode If this node has no right child, then this will be null

Since these instance variables are all private, remember to use getter/setter methods to access/modify them.

Method to implement:

public MyBSTNode<K, V> successor()

• This method returns the node with the smallest key that is still larger than the key of the current node. If there is no larger key, return null.
• Every node in our BST should / will already have the proper connections (parent and child references) with our sorted key property.
• Hint: Refer to zyBooks section 7.3 on how to implement successor if you are stuck!
• Important: You are not allowed to change the class signature! If you change the class signature, you’ll receive 0 for this part.

Part 1B: MyBST

The MyBST class is the public class of MyBST.java file. It represents a binary search tree where sorting is done based on the keys. This is not a self-balancing tree. Make sure you don’t change the class header, otherwise you will receive 0 points for the entire file.

MyBST has the property that all nodes in the left subtree of a node will have a key smaller than node.key, and all nodes in the right subtree of node will have a key greater than node.key. We will not be allowing duplicate keys in our tree, but we can have many different keys associated with the same value. We will be using the compareTo method to compare smaller/greater/equal keys.

Instance Variable	Description
MyBSTNode root	A reference to the root node of our tree. If the tree is empty, then this will be null.
int size	Represents the number of nodes in the tree.

Methods to implement (iteration and recursion are both allowed for this PA):

public V insert(K key, V value)

• If key is null, throw a NullPointerException.
• Insert a new node containing the arguments key and value into the binary search tree according to the binary search tree properties. Update the tree size accordingly.
• If a node with key already exists in the tree, replace the value in the existing node with value. (Example)
  • Note: We won't change the key of the pre-existing node.
• If a node with key already exists in the tree, return the original value replaced by value. Otherwise, if the insertion did not lead to a replacement (i.e., created a new node as a leaf, note that if the tree only has a root then the root itself is a leaf), return null.
  • Note: We overloaded the meaning of returning null as we’ve inserted a node with a new key into the tree, or that we have replaced the value of a node whose original value was null.

public V search(K key)

• Search for a node with key equal to key and return the value associated with that node. The tree structure should not be affected by this.
• If no such node exists, return null instead. Again, note that we've overloaded the meaning of returning null.
• Note: key might be null. We'll assume that no other key is equal to null (even though the compareTo() of type K might define this differently). This means that search(null) should always return null.

public V remove(K key)

• Search for a node with key equal to key and return the value associated with that node. The node should be removed (disconnected) from the tree and all references should be fixed, if needed. Update the tree size accordingly.
• When removing the node, if the node is not a leaf node, then we may have to make some changes to the tree to maintain its integrity. Make sure to fix all relevant references to parents/children.
  • For leaf nodes, no replacement is needed.
  • If the node has a single child, move that child up to take its place. (Example)
  • If the node has two children, then we will just overwrite the data at the node we plan to remove with the data from the successor, saving us the need to reconnect all the nodes if we had completely removed the node from the tree. Then remove the successor from the tree (this does not need to be done iteratively, you can do this with a recursive call). (Example)
• If no such node exists, return null instead. Again, note that we've overloaded the meaning of returning null.
• Note: key might be null. We'll assume that no other key is equal to null (even though the compareTo()of type K might define this differently). This means that remove(null)should always return null and not remove any nodes.

public ArrayList<MyBSTNode<K, V>> inorder()

• Do an in-order traversal of the tree, adding each node to the end of an ArrayList, which will be returned.
• After the entire traversal, this ArrayList should contain all nodes in the tree. These nodes will be sorted by the key order (with the smallest key at index 0) due to the order of the traversal.
• If the tree is empty, an empty (not null) ArrayList should be returned.
• Hint: it might be helpful to think about what the successor method does and how it relates to an in-order traversal. Using sorting algorithms is not allowed for this method.

public MyBST<K, V> copy()

• Copy the BST and return a new MyBST<K, V> reference that is an exact copy of all nodes (and connections between nodes) from the original tree.
• For each node in the copied BST, the corresponding key and value should remain the same but left, right, and parent may not point back to nodes in the original BST.
• We encourage you to implement this method using a preorder traversal.
• Hint: it might be helpful to think about using a helper method to recursively copy the nodes.

Part 1C: Testing (10 points)

We provide PublicTester.java, which contains all the public test cases we will use to grade your BST implementation (visible on Gradescope). See the comments in the file for test case details.

Your task: create CustomTester.java and implement tests that can correctly distinguish between good and bad implementations.

• Your tests will be graded by checking if they pass on a good implementation and fail on a bad implementation. If a test fails on a good implementation, then the test is written incorrectly. If a test passes on a bad implementation, it may be written incorrectly or may be not be rigorous enough (try adding more asserts).
• Gradescope will report whether your CustomTester fails on our good implementation (solution code) as a way to sanity check some of your test cases. However, you will not be able to see whether your tests pass/fail on the bad implementations until the PA is graded. Do your best to write comprehensive test asserts based on the write-up description and public tester examples.
• Any test you write in CustomTester.java will be run against all bad implementations. You will receive 1.25 points for every bad implementation your test is expected to fail, up to 10 points (if your test also passes on the good implementation).
• There is a total of 11 bad implementations for the following methods:
  • successor
  • insert
  • search
  • remove
  • inorder
  • copy

How to compile and run the testers:

Running the tester on UNIX based systems (including a mac):

• Compile: javac -cp ../libs/junit-4.13.2.jar:../libs/hamcrest-2.2.jar:. PublicTester.java
• Execute: java -cp ../libs/junit-4.13.2.jar:../libs/hamcrest-2.2.jar:. org.junit.runner.JUnitCore PublicTester

Running the tester on Windows systems:

• Compile: javac -cp ".;..\libs\junit-4.13.2.jar;..\libs\hamcrest-2.2.jar" PublicTester.java
• Execute: java -cp ".;..\libs\junit-4.13.2.jar;..\libs\hamcrest-2.2.jar" org.junit.runner.JUnitCore PublicTester

Part 1D: Coding Style (5 points)

Coding style is an important part of ensuring readability and maintainability of your code. We will grade your code style in all submitted code files according to the style guidelines. Namely, there are a few things you must have in each file/class/method:

• File header
• Class header
• Method header(s)
• Inline comments
• Proper indentation
• Descriptive variable names
• No magic numbers (Exception: Magic numbers can be used for testing.)
• Reasonably short methods (if you have implemented each method according to the specification in this write-up, you’re fine). This is not enforced as strictly.
• Lines shorter than 80 characters
• Javadoc conventions (@param, @return tags, /** comments */, etc.)

A full style guide can be found here and a sample styled file can be found here. If you need any clarifications, feel free to ask on Piazza.

Part 2: Sort Detective [10 points]

This assignment is developed from http://nifty.stanford.edu/2002/LevineSort/labWriteUp.htm

In this assignment, you are given a program which is designed to measure comparisons, data movements, and execution time for some of the sorting algorithms we discussed in class and in your readings: insertion sort, selection sort, merge sort and quicksort.

You may ask Professors/TAs/Tutors for some guidance and help. You can, of course, discuss the assignment with your classmates, but don’t just give away the answers!

The following files are provided for you and can be found in the starter repo:

| +-- SortDetective.java				
| +-- SortDetective.jar

You will submit the following file for this assignment:

• detective.json

As you know from class, if you double the size of the input data that you give to a quadratic algorithm, it will do four times the work; by contrast, an $O(n\ log(n))$ algorithm will do a bit more than twice as much; and, a linear algorithm will do only twice as much work. The properties of the input data set can affect the expected performance of many of our sorting algorithms. Before you begin, you should review the expected performance of the algorithms on various data sets.

1. Execute SortDetective.jar (to execute the program type java -jar SortDetective.jar at the command line, or double click the jar file in a file explorer), enter your PID on the top right corner and play with it a bit. Each of you would get a different matching based on your PID, and we will grade based on your PID as well. Create a list with some size and property of your choice by clicking "Create The List".
2. Click on each Greek letter under "Which Sort Is Which?" to see the number of comparisons, movement and running time of this execution under "Experimental Results". Notice that the Greek letters do not give any indication which sort they will execute.
3. As you click each Greek letter, take careful notes as you go. From your notes and the expected behavior of different sorting algorithms, match each Greek letter to some sorting algorithm and think about the rationale behind your guess.
4. Select the sorting algorithms for each Greek letter, and click on "Save to File" to export a json file named detective.json that you'll submit to gradescope. Make sure your PID is correct!
5. We have also provided SortDetective.java for you to know how we implemented each algorithm in SortDetective.jar and how we generate number of comparisons and execution time. Looking at the code is optional but encouraged, which is a review of how we can implement these algorithms, and moreover, make your guess more accurate.

Submission

Submit all of the following files to Gradescope by Tuesday, June 4th @ 11:59 PM PT.

• MyBST.java
• CustomTester.java
• detective.json

Note: Double-check the output to make sure your selections are accurate, including your PID. Your grade on the sorting part will be based on whether you’ve correctly identified the sort.

Important: Even if your code does not pass all the tests, you will still be able to submit your homework to receive partial points for the tests that you passed. Make sure your code compiles in order to receive partial credit.

How your assignment will be evaluated [100 points]

• Correctness [95 points] You will earn points based on the autograder tests that your code passes. If the autograder tests are not able to run (e.g., your code does not compile or it does not match the specifications in this writeup), you may not earn credit.
  • Tester [10 points]
    • The autograder will test your implementation of the JUnit tests.
    • This section has a maximum of 10 pts. This means if you pass at least 8 out of 10 custom tester cases, you will get full points for the Testing portion.
  • BST Implementation [75 points]
    • The autograder will test your implementation on the public test cases given in PublicTester.java and hidden test cases not described in this PA writeup.
  • Sorting [10 points]
    • You will receive 2.5 points for each correctly identified sorting algorithm.
• Coding Style [5 points]
  • MyBST.java will be graded on style. CustomTester.java will be graded on file, class, method headers and indentation.

Appendix

Insert an element

	Call to insert(100, "Niema"). Begin insertion of a node with key = 100 and value = "Niema".
	Go down the BST to find the place of insertion. First compare with the root. Since the key of the root (20) is less than 100, we go right, as indicated by the green arrow.
	We continue to go down the BST to find the place of insertion. Since the key of the right child of the root (95) is less than 100, we continue to go right, as indicated by the green arrow.
	Now we want to go left because the key at the current node (120) is greater than 100.
	We continue to go left because the key at the current node (105) is greater than 100.
	However, because a node with a key equal to 100 already exists in the BST, we will replace the original value ("Sander") with the new value ("Niema").

Remove a node that has a single child

	Call to remove(11). Before this step, we've already iterated down the tree to find where the node with key 11 is. Begin removal of the node with key = 11, and value = "Joe".
	Because the node we want to remove only has one child (the left child), we simply replace the node with its only child.
	We disconnect the original node from the tree and fix the parent pointer of the replacement (8:"Gerald") and child pointer of the parent (12:"Haytham"), completing the removal and replacement.

Remove a node that has two children

	Call to remove(95). Before this step, we've already iterated down the tree to find where the node with key 95 is. Begin removal of the node with key = 95 and value = "Paul". Note: the steps to locate this node are not shown.
	Since this node has two children, we want to first find its successor (the blue node) and replace the data (key and value) in this node with its successor's data.
	Now we replace the data (key and value) in this node with its successor's data, keeping all the parent/child references.
	The final step is to remove the successor and now we are done with removing a node with two children.