Assignment
You have to doONE of the following:
1. Modify your Registration project(s) to use a Hash Table to maintain the student information instead of the sorted array or BST. Your hash function should be based on the last three (3) digits of the student ID.
In your comments, include the average runtime for your Search, Insert and Delete methods, and how your program will handle collisions.
2. Adapt your Registration projects to include a menu (like in the warm-up project) that will determine, based on the "stability" of the registration data, the implementation of the student data (sorted array or bst). The project should include a way to change from the BST to the sorted array.
3. Write a program to calculate the probabilities of collisions for the following:
You are asked to write a program to store information for customers for a small local business. The owner wants to use "date of birth" (not the year!) as a way to look up customer information because he/she believes that the probability of collisions is very small.
Your program should calculate the probability of two customers having the same birthday, and finding
a. How many customers give a 50% chance of collision
b. How many customers give a 95% chance of collision
The program is not difficult, but be careful about the actual calculations (n! overflows for relatively small n)
Describe how you would handle collisions for the data, and also explain how you would write the "hash function" to assign a customer to the hash table by birthday.
4. Write a program that could be used to schedule jobs based on the "shortest job" algorithm, and compare the running of the programs to using a queue.
Use the data from the given table to calculate the "turnaround" time for each job (time a job is completed - time a job enters the system), and the average waiting time for the jobs ((total turnaround time - total "running" time)/number of jobs)
a) using a queue
b) using a heap based on "expected run time" (CPU burst)
Which method gives the lower average waiting time?