代写数据结构中的Hash Table, 并通过自动测试。
Learning goals
- Compare the efficiency of HashTable to Array and LinkedList
- Use Java’s HashSet and HashMap to solve real-world problems
- Write JUnit tests to verify proper implementation
Important: You won’t need to implement any hashing algorithms / data structures in this PA. Instead, you’ll need to use Java’s built-in HashSet and HashMap to complete this PA.
Overview
There are 4 parts to this assignment. All are required before the deadline and should be submitted on Gradescope:
- Part 1: Runtime Stimulation
- Part 2: Coding and Testing
- HashSet and HashMap Application
- Testing
- Coding Style
- Part 3: Conceptual Quiz
- Part 4: PA Reflection
Each part corresponds to its own Canvas “assignment” where your grade on that part will be recorded. Please complete all the parts individually; pair programming is not allowed for this PA. More information on submission is given in the Submission Instructions section.
Part 1: Runtime Stimulation
You are given 3 mystery data structures, which are implemented in MysteryClassA, MysteryClassB, and MysteryClassC. Your goal is to analyze the runtimes of their operations in order to help you classify the type of data structure each class has implemented. You will do this using the following steps (more information for each is given below):
- Connect to ieng6 and then run and time the methods below on different input sizes.
- Copy your timing information into a spreadsheet that will graph your results.
- Based on these graphs and your knowledge of Big-O running time of different operations for different data structures, answer questions on gradescope about what data structure each class implements.
Each class has an add method, a find method, and a remove method. Here is the set of operations you will be given.
| Data Structure | add | find | remove |
|---|---|---|---|
| ArrayList | Add the element to the beginning of the list (index 0). | Find the given element. | Remove the first element. |
| LinkedList | Add the element to the beginning of the list (index 0). | Find the given element. | Remove the first element. |
| HashTable | Add the element according to hashing rules. | Find the given element. | Remove the given element. |
Connecting to Your ieng6 Account
The mystery classes are provided as a jar file on ieng6, called simulatior.jar. Look up your course-specific account for CSE 12 here. Your CSE 12 account is different from your CSE 15L account, and it should start with cs12wi22. Then you can connect to ieng6 using ssh. Your command will look like this, but with the zz replaced by the letters in your course-specific account.
Note: Since CSE 15L is a co-requisite of CSE 12, we do expect you to be familiar with working in a Linux machine over SSH. If you don’t know how to do so, please refer to CSE 15L Week 1 Manual. Additionally, you may go to the CSE basement labs to complete this assignment.
Running the Simulation
Use the following line in your terminal in order to run the simulation. You’ll need to provide 5 command line arguments, as specified below.
$ java -jar ../public/bin/simulatior.jar --data-structure [ds] --size [size] --operation [operation] --iteration [iteration] --round [round]
- –data-structure
- Select A, B, or C for the version of the method corresponding to MysteryClassA, MysteryClassB, or MysteryClassC.
- –size
- This represents the number of elements the data structure has.
- –operation
- Select add, find, or remove to run the corresponding method.
- –iteration
- This represents the number of times the given operation is run in one trial.
- –round
- The number of trials represents the number of times the operation is tested and timed. An average time across all the trials will be reported at the end.
Example
$ java -jar ../public/bin/simulator.jar --data-structure A --size 40000 --operation remove --iteration 500 --round 2
The above command runs MysteryClassA’s remove method and the object has 40000 elements. Each trial calls remove for 500 iterations with randomized arguments, which is then repeated for 2 rounds.
The following is an example of the expected output from running the above command. Your reported time values may vary within a reasonable range.
Warmup rounds (will be ignored in the average)...
Total time (for 500 operations): 360.2340 us.
Average (for a single operation): 0.7205 us.
Total time (for 500 operations): 247.2960 us.
Average (for a single operation): 0.4946 us.
Round #1 (out of 2)
Total time (for 500 operations): 210.7010 us.
Average (for a single operation): 0.4214 us.
Round #2 (out of 2)
Total time (for 500 operations): 196.7730 us.
Average (for a single operation): 0.3935 us.
Average (for a single operation over 2 rounds): 0.4075 us (this is what you need for the next section: Collecting Data)
Collecting Data
You will be required to run the simulation for all the mystery data structures A, B, and C, with size of 10000, 20000, 30000, and 40000, calling all the operations add, find, and remove, for 1000 iterations and 5 rounds. (So there are 36 different combinations of simulation in total). Record the average runtime each time and plot the data using a Google spreadsheet template.
Make your own copy of the template in order to enter your data values (“File” > “Make a copy”). Enter your data in the appropriate cells that are colored yellow, and the plots will automatically update. You should enter the average time reported from your 5 trials in microseconds (us) for your data. You should not edit any other part of the spreadsheet. Then upload a PDF (“File” > “Download” > “PDF”) of your sheet in Q2 Collecting Data section on Gradescope.
Identifying the Mystery Classes
In the Gradescope assignment for part 1, categorize each Mystery Class as either a HashTable, ArrayList, or LinkedList. For each choice, you are required to analyze its big-O runtime behavior and justify your answer based upon the data you collected from the simulation.
Part 2: Coding and Testing [7 points] (individual)
In this part of the assignment, you will directly use Java’s built-in data structures and write JUnit tests to ensure that you call the functions correctly.
Make sure to read the entire write-up before you start coding. you may not change any public class/method or variable names given in the write-up or starter code.
Download the starter code from here and put it in a directory in your working environment.
Part 2a: HashSet Application
It’s time to register for classes again, and we need to organize the students and courses during the enrollment period.
You will be using a HashSet to help you track course enrollment. Refer to the Java documentation for more information on HashSet. You are allowed to use any of the methods listed in the documentation for Java’s HashSet directly.
Student
You will first complete the methods to implement the Student class. Student objects will be stored in Course objects.
All variables should be declared as private final. Think about what will happen to the hash code if you allow those elements to be changed after initialization.
| Instance Variable | Description |
|---|---|
| String firstName | A string representing the first name of the student. |
| String lastName | A string representing the last name of the student. |
| String PID | A string representing the PID of the student. |
This is unique for each student.|
You will be required to implement the following methods.
| Method Name | Description |
|---|---|
| public Student(String firstName, String lastName, String PID) | Initialize the student’s information |
| public String getFirstName() | Return the student’s first name |
| public String getLastName() | Return the student’s last name |
| public String getPID() | Return the student’s PID |
| public boolean equals(Object o) | Returns true if o is also a non-null Student and all the instance variables of o equal the instance variable of the current Student object. Otherwise, return false. |
| public int hashCode() | Return the hash value generated by Object’s hash function. The hash function should generate a hash value in the order of the student’s firstName, lastName, and PID. See an example here. |
| public int compareTo(Student o) | Returns 0 if all the instance variables are equivalent. Returns a negative value if the current object lexicographically comes before Student o. Returns a positive value if the current object lexicographically comes after Student o. The order of precedence for instance variables is lastName, firstName, and PID. You should use .compareTo to compare those strings. Do not implement any char-wise comparison logic. |
Course
Our Course class will help us store the students registered for this particular course in the form of a HashSet.
All variables should be declared as private final except for enrolled.
| Instance Variable | Description |
|---|---|
| HashSet | This is a collection of students that are enrolled in this course. |
| int capacity | This is the maximum number of students that can be enrolled in this course. |
| String department | This course falls under this department. |
| String number | This is the course number. |
| String description | This is the description of the course. |
Part 2b: HashMap Application
A wildlife sanctuary needs your help to efficiently track the animals that are in its care! The sanctuary wants to keep track of how many of each species are currently located on its grounds.
You will be using a HashMap to help you organize all the animals at the sanctuary. Refer to the Java documentation for more information on HashMap. You are allowed to use any of the methods listed in the documentation for Java’s HashMap directly.
| Instance Variable | Description |
|---|---|
| HashMap | Container to store all the animal species in the sanctuary. The String represents the name of the animal species and the Integer represents the number of that species at the sanctuary. If String is null or Integer equals to 0, the species should not be in the sanctuary HashMap. |
| int maxAnimals | The maximum number of animals that the sanctuary can support. |
| int maxSpecies | The maximum number of species that the sanctuary can support. |
Part 2c: Testing
We provide two test files:
- PublicTester.java
- Contains all the public test cases we will use to grade your HashSet and HashMap application (visible on Gradescope).
- CustomTester.java
- This file contains 10 generic method headers. You will edit this file. Points will be deducted if method header descriptions are not completed.
Your task in this part is to implement the tests that are stubbed out in the custom testers. Here are the rules for how you must follow:
- Your tests must test the method they are named for, but they may test any aspect of that method’s behavior that is not already covered by a test in the public tester. Points are awarded only if your test cases cover cases that the public tester file does not take into account.
- There is no restriction on what error message you use as your string input.
- You MUST NOT copy code from the public tester file.
- DO NOT CHANGE THE TEST METHOD NAMES OR REMOVE ANY OF THE GIVEN 10 METHODS.
- You may add additional test methods, but you are not required to do so.
- Make sure all the test cases in the custom tester file pass. Otherwise, you would receive 0 points for the test case that fails.
The table below gives the list of public tests that we will run against your solution. We will also test your code on additional hidden tests, but we will not tell you what the hidden tests will do. Note that some methods are not tested in the public tester, but will be tested using the hidden tests. It is your responsibility to write your tests to thoroughly test your code, including all edge cases.
How to compile and run the public tester
on UNIX based systems (including macOS):
$ javac -cp libs/junit-4.12.jar:libs/hamcrest-core-1.3.jar:. PublicTester.java
$ java -cp libs/junit-4.12.jar:libs/hamcrest-core-1.3.jar:.org.junit.runner.JUnitCore PublicTester
on Windows systems:
$ javac -cp ".;libs\junit-4.12.jar;libs\hamcrest-core-1.3.jar" PublicTester.java
$ java -cp ".;libs\junit-4.12.jar;libs\hamcrest-core-1.3.jar" org.junit.runner.JUnitCore PublicTester
| Student Test Cases | Public Cases |
|---|---|
| constructor | Valid argument constructor |
| equals | Evaluate equivalent Student objects |
| hash | check if the hash is deterministic |
| Course Test Cases | Public Cases |
|---|---|
| constructor | Valid argument constructor |
| enroll | Enroll a new non-null student |
| unenroll | Unenroll an existing student |
| isFull | check a full roster |
| toString | Get a descriptive string from a normal course |
| Sanctuary Test Cases | Public Cases |
|---|---|
| constructor | Valid argument constructor |
| getNum | Get the number of animals of a species at the sanctuary |
| getTotalAnimals | Get the total number of animals at the sanctuary with one species |
| getTotalSpecies | get total number of species at a sanctuary with some species |
| rescue | Add a new species of animals to not-full sanctuary |
| release | Remove some animals from the sanctuary |
Part 3: Conceptual Quiz
You are required to complete the Conceptual Quiz on Gradescope. There is no time limit on the Quiz but you must submit the Quiz by the PA deadline. You can submit multiple times before the deadline. Your latest submission will be graded.
Part 4: PA Reflection
Complete the PA5 reflection. There is an automatic 36-hour grace period for this part.