Purpose & Goals
Generally, the assignments in this course are meant to give you the opportunity to practice with the topics of this course in a way that is challenging yet also manageable. At times you may struggle and at others it may seem more straight-forward; just remember to keep trying and practicing, and over time you will improve.
Specifically, assignment 4 aims to improve your understanding of the (Unsorted) Set interface and sorting algorithms by:
- Using the Hashtable, HashMap, sorting algorithms, and any interfaces from previous assignments to solve a variety of problems (Part A),
Implementing some new methods in the MyStrictHT, and HCPractice classes (Part B)
Part B: The Implementation
The (provided) StrictHT and MyStrictHT classes are implementations of the Set interface via a hashtable that has a strict/constant number of buckets (as opposed to our usual kind that adds more buckets as the load of the hashtable hits a certain threshold.) StrictHT is the basic implementation that you do not and should not modify. MyStrictHT is a child class of StrictHT that you can and should modify in order to better implement the Set interface (with regards to time). More details below in question 5. The Person class (within the HCPractice class) is an (incomplete) implementation of the Person class, in that it will not allow us to correctly create a Set of Persons without duplicates. Your task is to complete its implementation so that we can create such a Set. More details below in question 6. Default implementations are provided for both questions 5 and 6, but they will not pass the server tests.
- [14 marks] In the MyStrictHTclass, make changes to any of the StrictHT non-final methods (by overriding them in MyStrictHT) as you see fit in order to pass the (time) performance server tests. MyStrictHT is a child class of StrictHT, so it will compile and run and be correct right out of the gate; the default implementation, however, will not pass the server performance tests because it is too slow. Your task is to determine what makes the methods so slow in this “strict” setting, and make improvements.
Note that some inherited methods and variables are final so that they cannot be changed; this is on purpose to try to prevent you from taking certain shortcuts I don’t want you to take. Anything that is not final can be overridden in MyStrictHT and implemented as you see fit. Do not make changes to StrictHT, as a local copy (not yours) will be used on the server.
Also note that the main methods in StrictHT and MyStrictHT are the same, and they start off by taking ~10s each (on Prof Alexa’s local machine.) The fastest implementation I have can run these tests in <2s, for reference, and a ~5s solution will pass most, if not all, server tests.
This is a more open-ended question than we’re used to; this is intentional! It’s meant to give you flexibility to apply one of many possible solutions, so try to relax and think critically about the existing code and how you can improve upon it.
If it helps, I will only test this on types T that are Comparable (e.g. Integers, Strings).
If you want to run MyStrictHT.main with the assertions, use the -ea parameter, e.g.
% java -ea comp2402w22a4.MyStrictHT
- [13 marks] In the Personclass (within the HCPractice class), implement the equals and hashCode methods so that we can correctly store a Set of Persons without duplicates, that is, we want to be able to add, remove, and find distinct Persons. Each Person has 4 characteristics:
fname – first name – we assume this is constant over the course of the program
lname – last name – we assume this is constant over the course of the program
birthYear – year of birth – we assume this is constant (!!)
luckyNumber – a person’s lucky number, if they even have one. This can change
over the course of the program
There are some basic tests in the HCPractice.main that you should examine and play around with. If you want to run HCPractice.main with the assertions, use the -ea parameter, e.g.
% java -ea comp2402w22a4.HCPractice
EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!
E-mail: email@example.com 微信:easydue