In this project, you will implement two common structures for storing data for efficient searching. Then you will design and implement a solution to a specific problem given in Part 3.
In this part, you will implement a basic hashtable (from scratch). The keys for this hashtable are Strings, and you can use Java's built-in hashcode function for strings. You have three options for implementing the hashtable. The values are integers (use the Integer wrapper class).
In all options, you should implement the hashtable to resize (and rehash) based on a load factor. In all options, resizing to a larger size should make the table size to be the first prime number greater than or equal to twice the original size, and resizing to a smaller size should make the table size to be the first prime number greater than or equal to the floor of half the original size. You should also make sure you table size is always initialized to be a prime number.
Example: m = 7
resize to larger: m = 17
resize to smaller: m = 3
Option 1. Separate Chaining
This is probably the easiest way to implement a hashtable and so, if you choose this option, you have the opportunity to earn up to 80% of the points for this part. That is, the points you earn will be multiplied by 0.8.
You may use ArrayLists to implement the chains, but be careful how you add items as you need to remember that ArrayLists are built on arrays, and you don't want to force them to do anything unnecessarily inefficient.
It is up to you to choose an appropriate load factor threshold, but make sure you resize both when the load factor gets both too big or too small.
Option 2. Linear Probing
If you choose this option, your table should be a simple array that uses linear probing as discussed in class. You should resize to larger when a > 1/2 and resize to smaller when a < 1/8. With this option, you can earn up to 100% of the points in this section.
Option 3. Quadratic Probing
If you choose this option, your table should be a simple array that uses quadratic probing as discussed in class. You should resize to larger when a > 1/2 and resize to smaller when a < 1/8. This option is not that much more difficult than Option 2, but < 1/8. there is the added issue of a possible infinite loop, so if you do this option, you can earn up to 104% of the points in this section. That is, the points you earn will be multiplied by 1.04.
For all options:
Implement your hashtable in a file called Hashtable.java and include all the following methods.
| Method Signature | Description |
| Hashtable() | constructor; assign a reasonable starting capacity to the table (not too big, not too small), make sure it's a prime number |
| Hashtable(int m) | constructor; create an empty hashtable with the starting capacity as m, which sould be a prime number; you do not have to enforce that it is a prime number at this point |
| void put(String key, Integer val) | put (key, val) into the table according to how your particular implementation choice was discussed in class; check the load factor and resize if necessary |
| Integer get(String key) | retrieve the Integer value that is paired with the given key; return null if the key is not in the table |
| Integer delete(String key) | delete the item from the table that is paired with the passed key and return the value associated with the said key or null if the key is not in the table; be especially careful with this if you chose Option 2 or Option 3! |
| boolean contains(String key) | return true if the table contains the given key and false else |
| boolean isEmpty() | return true if the table is empty and false otherwise |
| int size() | return the number of (key, value) pairs in the table |
In this part, you will implement an ordered symbol table by implementing a search tree. Here, the keys are Integers and the values are Strings. Again, you have two options, which are graded differently as they differ in difficulty.
Option 1.
Build a regular binary search tree. This should be implemented as discussed in class. If you choose this option, you can earn up to 80% of the points for this section. That is, your earned points will be multiplied by 0.8.
Option 2.
Build a right-leaning red-black tree. A right-leaning red-black tree is like a left-leaning red-black tree except that all the red links must lean right (instead of left). If you choose this option, you should start by working out each of the cases by hand first to make sure you know how this tree works. If you understand the cases for left-leaning red-black trees, this one is basically just the opposite, and you don't have to change the basic transformations (e.g. rotateLeft, rotateRight, and colorFlip). Note that the code for these, as well as for a Node is provided in the slides, and you may copy that directly. However, you should be very wary of looking up other implementations. I assume this is the first time you have implemented a red-black tree of any kind, and your implementation is probably not going to be very streamlined. If it is, that would be a serious red flag. The point of this is for you to work through the implementation to help you more fully understand the structure, so dont sell yourself short by taking a shortcut!
The good news!
| Method Signature | Description |
| Tree() | constructor; create an empty tree |
| void put(Integer key, String val) | put (key, val) into the tree according to how your particular implementation choice was discussed in class |
| String get(Integer key) | retrieve the String value that is paired with the given key; return null if the key is not in the table |
| boolean contains(Integer key) | return true if the tree contains the given key and false else |
| boolean isEmpty() | return true if the tree is empty and false otherwise |
| int height() | return the height of the tree |
| int height(Integer key) | return the height of the node containing the given key or -1 if the key is not in the tree |
| int size() | return the number of nodes in the whole tree |
| int size(Key key) | return the number of nodes in the subtree whose root contains the given key or -1 if the tree does not contain the key |
Note: A common mistake (in terms of efficiency) is to re-calculate the height/number of nodes each time such methods are called. Instead, you should keep track of these values as you insert nodes. The Node class in the slides already has an N-value which represents the number of nodes in that subtree. You should also include a height value and make sure these things get updated when you do inserts. If you do this less efficiently, you may not get full credit.
In this part, you will design and implement a program to manage submissions for an ongoing programming competition. The programming competition is ongoing, and contestants can submit different parts at different times. Thus, there must be a way to update their scores. We also will want to have other functionality. Each contestant will be identified by their name (a String) and will have a numerical (Integer) score associated with them. You are provided with a Contestant.java file that represents a contestant, as well as SortContestants.java, which ensures that lists always get output in the same order for testing purposes. This is an open competition so people can join at any time. Thus, you do not know how many contestants there will be total, and you do not know who they are until they make their first submission. The actual functionality that is required is below. Your job is to design a system that will allow all the required functionality, taking efficiency into account. Most likely, you will need multiple data structures.
You are allowed to use any of the following:
Note on using the classes mentioned above from java.util: If you use any of those classes, make sure you read the information in the links, which provides implementation details, including runtime. Since you will need to analyze your functions for runtime, you will need to understand how these classes are implemented.
Implement your solution in a file called ScoreDB.java and make sure that all of the methods below are included.
| Method Signature | Description |
| ScroreDB() | constructor |
| put(String name, int score) | add or update the score for < name>; since what is stored is a running total, < score> should be added to the existing total if < name> is already in the database |
| int getScore(String name) | return the current score for < name> or null if < name> is not in the system |
| int getRank(String name) | return the rank of < name> in the competition or -1 if < name> is not in the database; note that there may be ties, and anyone with the same score should be considered with the same rank Example: Current values in database: (Mary, 45)--rank is 2 (Joe, 89)--rank is 1 (Steve, 12)--rank is 3 (Howard, 89)--rank is 1 (Quentin, 45)--rank is 2 |
| ArrayList< Contestant> higherThan(int threshold) | return a list of names of people whose scores are greater than or equal to the threshold; this list should be sorted in ascending order by score; return an empty list or null if no contestants meet the criteria |
| ArrayList< Contestant> lowerThan(int threshold) | return a list of names of people whose scores are less than or equal to the threshold; this list should be sorted in descending order by score; return an empty list or null if no contestants meet the criteria |
| ArrayList< Contestant> top(int n) | return an array containing the top n contestants by score, sorted in ascending order by score; if n >= the total number of contestants, return a sorted list of all the contestants; if there are ties that make it so that there are not exactly n that fit the criteria, return the least number that you can include that still include the top n; for example, if n = 5, and there are 8 people with the top score, return all 8; return an empty list or null if there are no contestants |
| ArrayList< Contestant> bottom(int n) | return a list of the bottom n contestants by score, sorted in descending order by score; if n >= the total number of contestants, return a sorted list of all the contestants; if there are ties that make it so that there are not exactly n that fit the criteria, return the least number that you can include that still include the bottom n; for example, if n = 5, and there are 8 people with the bottom score, return all 8; return an empty list or null if there are no contestants |
| int numContestants() | return the number of contestants currently in the competition |
| ArrayList< Contestant> max() | return the Contestant(s) with the highest score; return an empty list or null if there are no contestants |
| ArrayList< Contestant> get(int rank) | return the Contestant(s) currently at rank < rank>; return an empty list or null if there are no contestants |
1. Analyze the runtime of each of the required functions in ScoreDB.java. You only need to consider the worst case unless the worst case is very different from the average case and is unlikely to happen. (For example, using expected runtime for a hashtable is more useful than using the worst case.) In that case, you should discuss both the worst case and the expected runtime.
2. Let N be the number of scores that come in while the competition is open. (Note that this is the number of scores (including both new contestants and score updates), not the number of contestants.) Analyze the total runtime of processing all N scores for both the best and the worst case.