Description
Between the strain put on its resources by the recent pandemic and the govern-ment’s lack of desire to lend it a hand, the United States Postal Service is under threat of a full-on collapse. A government appointed panel has been dispatched to analyse the day-to-day operations of the giant public service provider, and has found a major bottleneck in its mail tracking software. Upon in-depth anal-ysis, it was found that the underlying algorithm in the software is utilizing a Linked List for inserting and searching all of its shipments, taking an enormous amount of time, especially when working under increased demand as of late. The panel knows that it is best to make important decisions based on objective data. Can you help set up an experiment to gure out which data structure will solve the software bottleneck, helping return USPS to its former glory?
Linked List: one gure for dataSetA, one gure for dataSetB
Binary Search Tree: one gure for dataSetA, one gure for dataSetB
Hash Table with chaining: one gure for dataSetA, one gure for dataSetB
Hash Table with open addressing, linear probing: one gure for dataSetA, one gure for dataSetB
Hash Table with open addressing, quadratic probing: one gure for dataSetA, one gure for dataSetB
A summary gure, for the inserts. Here you should pick the best of the hash table results. Plot the inserts for the chosen hash table, the linked list, and the BST.
A summary gure, for the searches. Again pick the best of the hash table results. Plot the inserts for the chosen hash table, the linked list, and the BST.
As an example, your Linked List plots should look similar to gure 1. For your nal report, you should have a single plot showing the given data, then each of the gures described above, resulting in a total number of 13 gures.
Figure 1: Average insertion and search times for a Linked List with Data Set A
4.3 The Report, Submission, and Interview Grading
Provide a concise summary of your ndings in a report along with all of your gures. Describe which data structure you nd to be the best for the USPS package tracking application. Refer to the di erent data types and provide some hypothesis as to why the di erent data structures perform better or worse. Your report can take up multiple pages due to the gures, but try to limit your write-up to 500 words.
Submit all of your neatly commented code for each data structure imple-mentation, along with a driver le for each experiment. You can choose to work alone or with a partner. If you choose the latter, list the authors in your .hpp le, describing each team member’s contributions. If you would like to work with a student from a di erent recitation section, you and your partner must consult with your respective TAs for approval.
There will be mandatory interview grading for this project. It is the students’ responsibility to schedule an interview with their TA (if working with another student, only one interview is necessary with either student’s TA).
-
Extra Credit
Come up with a data structure that performs better on all fronts than any of the mandatory ones. You must make a solid case backed by results and analysis showing the superiority of your approach. Of course, you have to code up the data structure yourself, not just use an external library. You will be eligible to receive 5 to 10% points if you meet the challenge, per your TA’s discretion.
6
