# CS 249 Project 4 - Radix Sort & Binary Search Trees

Radix Sort & Binary Search Trees

Project Goals The purpose of this project is to: 1. Ensure that you can implement a non-comparison sorting algorithm 2. Ensure that you can implement a binary search tree
Project Objectives To achieve the above goals, students must be able to: 1.Write Java code that adheres to best practices (e.g. abstraction) and OOP. 2.Write unit test cases which validate and verify program integrity. 3.Implement the Least-Significant-Digit Radix sorting algorithm. 4.Implement a generic binary search tree. 5.Analyze the efficiency of all non-test code using Big-O notation. Instructions
Part A: Radix Sort Implement a radix sort as described in the last section of Chapter 7 in your text. It
should handle variable amounts of data and variable numbers of digits in the key
values. Use testing to ensure radix sort works for at least three examples of
different input sizes and various max digit length.
Part B: Binary Search Tree
Implement a Generic Binary Search Tree.

Use this tree to hold Student objects.
Students should be arranged based on their GPA. Write a main method showing
you can insert, find and delete Students without violating the BST property. You
will need to use the Comparable Interface to compare Students.
Refer to the Interfaces given for both parts of this assignment.
Project 4 Rubric – 100 pts 20 points – Design
+7 pts - Appropriate scope: reasonable breakdown of functionality, private class
variables.
+6 pts - Appropriate Naming conventions: variables, methods, files
60 pts – Implementation
30 pts - Part I: Radix Sort
+15 pts - Method sortRadixLSDOnePass(int[]) provides correct behavior, allowing
each step of the Radix algorithm to be compared in testing.
+15 pts – Method sortRadixLSD (int[], int maxsigdig) provides correct output,
correctly sorting the input array when tested.
30 pts – Part II: Generic BST
+5 insert(key,value) works for a single input to the tree
+5 insert(key,value) works when multiple values are added to the tree
+5 find(key) works for a tree with a single key/value pair
+5 find(key) works for a tree with multiple key/value pairs
+10 delete(key) works for all deletion cases
.
20 pts – Write Up and Submission
+2 pts for screen shots
+3 pts Java files submitted: correct file types submitted.
+3 pts for execution instructions: 1 points per part (parts A, B, and C)
+4 pts for identify who you collaborated with, how and why it was beneficial
+8 pts for correct efficiency: 3 pts Part I and 5 pts Part II (i.e., 1pt for each of the
following – insert, delete, find, display, comparing Nodes/Student objects.