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

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

+7 pts - Readability: comments, white space, indentation

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.

+7 pts - Appropriate scope: reasonable breakdown of functionality, private class

variables.

+6 pts - Appropriate Naming conventions: variables, methods, files

+7 pts - Readability: comments, white space, indentation

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.

You'll get 1 file (14.0KB)