Computer Science Programming Homework

1/4

Data Structures and Algorithms, CS146, Spring 2019

Programming Assignment 4 BST and RB Tree Social Security Numbers

Due at 11:59pm, on May 21st (Tuesday), 2019

(This programming assignment is optional and for up to 5% extra credits. No late submission!)

Warning: This programming assignment is for individual work only. You are not allowed to use someone's code or copy from internet, except for Web Crawler code provided. Code plagiarism checker tools (Jplag, MOSS, etc.) will be used to check the similarity of codes. You may be asked to demo and explain your code to the instructor or to the class. Cheating will not be tolerated and will be reported to University. Please check on the University Policies in the syllabus. Read this instruction carefully before your design and implementation of your work. Problem Statements US Social Security Administration uses Social Security Number (SSN) to identify and keep track of persons who are eligible for social benefits such as retirement pension, medical insurance support, etc. Assuming that there are 20 persons only in a group who are eligible for social retirement benefit. You are developing a SSN application for administrators at SSN office to dynamically process these 20 Social Security Numbers. Functional Requirements

For this programming assignment, your job is to design and implement Binary Search Tree and Red-Black Tree to dynamically insert, delete, search, sort a set of SSN based the above Social Security Numbering schema in the format of “Name XXX-XX-XXXX”. You must use the following 20 names who are retiring: Mike Jane James Marry Ben Mason Elijah Oliver Jacob Lucas Michael Sofia Ethan Daniel

2/4

Matthew

Ella

Henry

Victoria

Jackson Ken

The following major features must be implemented:

(1) Retirement Binary Search Tress (BST): . (a) Use a random number generator to generate 20 SSN for the 20 retiring persons and build

up a Retirement BST by names and based on SSN. Make a list of retirement persons in the format: Name XXX-XX-XXXX 
(Draw the BST you just created) (-20 if this is not implemented)

.

. (b) Insert a name to the Retirement BST based on his/her SSN. (-10 if this is not implemented)

.

. (c) Delete a person from the Retirement BST. 
(-10 if this is not implemented)

.

. (d) Visit each node In-Order to make a sorted list of retiring people according to the SSN from the BST. 
(-10 if this is not implemented)

. (2) Retirement RB Tree: . (a) Modify BST Three from (1) and build up a Retirement RB Tree. The color property of

each node must be presented. (MUST follow RB Tree properties specified in textbook and ppt slides. Your own tree structure will not be accepted.) (A better way to verify if your RB tree is correct or not, just draw the RB tree.) 
(-20 if this is not implemented)

.

. (b) Allow users to insert a Name to the Retirement RB Tree based on SSN. (Must list the Name and SSN showing that the node has been inserted into RB Tree and must draw the RB tree to show the result of the color property changes of URL nodes) 
(-20 if this is not implemented)

. (c) Allow users to search a Name in the retirement group by entering a SSN. 
(-20 if this is

not implemented) Programming Requirements

1. This PA4 be written in Java.

2. Each java file/class/subroutine/function call MUST contain a header comment at the

beginning of each and make sure you have enough comments at the end of lines in your code.

(-20 points if your code did not provide enough comments.)

3/4

3. You MUST write a professional/formal report in MS Word/PDF format with the following

items included in the report: (You will receive 0 point for this assignment if a report is not

provided.)

a) Cover Page – PA4 Title and your name (-10%)

b) Design and Implementation: (Ranging -20% ~ -40%)

Briefly explain/illustrate how you design and implement such as diagram, graph, data

structure, (Array, ArrayList, Linked List, Vector, etc.).

c) A list of classes/subroutines/function calls: (-10%~30%)

Explain purpose for each.

d) Self-testing screen shots: (ranging -50% ~ -100%)

Provide enough screen shots for each function including inputs and outputs for each

of function listed in “Functional Requirements” section. This is to verify your codes

and to check to see if your codes match the functional requirements and run correctly

by yourself. (You will receive 0 point if no self-testing screenshots provided. Points

will be taken off if not enough self-testing screen shots provided.)

e) The procedure (step by step) of how to unzip your files, install your application, and

run/test your codes. (-20% if not provided)

f) Problems encountered during the implementation: Describe all problems

found/encountered during your implementation and how you resolved them. (-30%

if not provided or too simple.)

g) Lessons Learned: Describe the concepts and skills you have learned from this

programming assignment and any inspiration or motivation you got from this

programming assignment. (-30% if not provided or too simple.)

Submission Requirements:

1. Zip all your files including your formal report, all *.java files, and a Java executable file (a jar file, so that I can run your code) into one zipped file with file name: PA2-Secion 8- Last_Name.zip, Any file with incorrect file name will not be accepted and 0 point will be given. [No jar file or your code is not runnable (test it before submission: java -jar filename.jar): -20 points]

2. The deadline to submit/upload your zip file to Canvas is before 11:59pm on Tuesday, 5/21/2019. After deadline, the submission link will be closed.

4/4

Warning: DO NOT wait until the last minute to upload your files to Canvas. It has been

happening all the time that it took forever to upload files to Canvas during the last

hour/minute. No excuse for late submission.

Grading Criteria

Grading is based on the creative design, full functioning, completeness and clarity of codes and the professional report. Each grading policy is specifically listed after each functional item above. You should follow the functional requirements to avoid losing points. Extra bonus points will be given to additional/excellent work.

Note: Eclipse with JDK 8 under can export project into Runnable Jar, but not JDK 9.