CSC122F2020BSTree < CenterForComputing

Tags: view all tags
---++Binary Search Tree and Hashing Lab
---+++Overview
There are three components to this lab.   You are studying time to look up a student for an institution.  You are to compare hashing, BST, and just sort with a binary search.
---+++Details
You can have up to 100,000 students.  Each student has an unique id.  Make the id's similar to Bethel's.  For the sort, use the merge sort.  For the binary search, you may chose to implement it with iteration or recursion.  You are to count the number of compares as you build the structure and then as you look up students.  Vary the number of lookups to 5% of the population, 50% of the population, 100% of the population, 1000% of the population.  Vary the input based upon the order of the data (in order, random order, reverse order).  You may also vary number of students if you wish.
---+++Components
This lab is divided into two parts:<br>
<b>Part 1: Design</b>  For this part develop a design for the lab.  Since you are implementing the hash table and the binary search tree, you need a UML class for each one.  Also include one for the simple structure (array that gets sorted).  Include methods to help with the counting.  Turn in things similar to the previous design labs including a well designed testing plan.<br>
<b>Part 2: Implementation</b>  For this part you implement your structures and write up a comparison of the amount of work based on your testing data.
---+++Extra Credit
   1. Also compare the heap sort, the selection sort, and the insertion sort.
   1. Compare the bubble sort after finding and adding at least one way to improve its efficiency
Topic revision: r1 - 2021-11-03 - cathybareiss