Due: 11:59pm ET Tuesday, March 21, 2023

Reminder

•    IMPORTANT: No late work will be accepted without permission in advance from the instructor before the due date. Everyone has 1 (one) chance during the semester to submit homework late.

•    All work submitted under your name must be your own. See Pace University's Academic Integrity Code (PDF).

Instruction

•    This assignment contains 3 parts of programming exercises consisting of 10 questions in total.

•    Download ZipcodeHashtable.java and zipcode.csv; write the code directly into ZipcodeHashtable.java.

o  All codes must compile; the codes that don’t compile will result in 0 (zero) point.

•    After completing the exercise, compress back the files into .zip; name the .zip file in following format: {U-ID}_{FirstName}_{LastName}.zip.

•    Upload the file to the assignment section of the course homepage at https://classes.pace.edu.

Programming Exercises

All the answers to programming exercises in this homework assignment must be written in ZipcodeHashtable.java. Part 1: Sort & Search [Total: 25 pts]

1.   Fill in the method readDataFile that reads each line of a CSV file into a Zipcode object and returns an ArrayList that contains the Zipcode objects created. [5 pts]

a . You MUST use the data file provided in the zip file: zipcode .csv .

b.   You may modify sc = new Scanner(new File("zipcode .csv")); to be able to read the given csv file.

2.   Fill in the method selectionSortByDecrementingZipcode that uses Selection Sort to sort Zipcode objects in decreasing order. [ 10 pts]

a.    compareTo method in Zipcode object will sort the objects in increasing order, when used as-is. You must use compareTo method correctly to sort the objects in decreasing order.

b.    For example,

i.    Increasing order of zipcode: “10001” à “10002” à “10003”

ii.    Decreasing order of zipcode: “10003” à “10002” à “10001”

3.   Fill in the method binarySearchZipcode that take a sorted ArrayList of Zipcode objects and a zipcode as an input; the method must return true if the zipcode is found, false otherwise. Assume that the ArrayList has

Zipcode objects sorted in decreasing order. [ 10 pts]

Part 2: Build Your Own Hashtable [Total: 50 pts]

1.   Fill in the method hashCode of Zipcode object that will be used to determine which bucket in a ZipcodeHashtable to place the object in. [5 pts]

a.    The hashtable will have 5,273 buckets (i.e., use ‘mod 5273’ to identify the bucket number).

b.   The hash code calculation will use zipcode attribute only, which has 5 characters. Think about how you can write this into JAVA code form.

ℎasℎCode = )ZipCode[4 − i] × 37i 5 mod 5273

c.    The hash code may turn out to be a negative number; if that happens, add 5,273 to the final value to make it positive.

2.    Fill in the constructor of ZipcodeHashtable class. [5 pts]

a.    Initialize internalTable variable to be the array of LinkedList<ZipCode> with the size of 5,273 (indicating 5,273 buckets).

b.    Initialize size variable to be 0, since when initialized the hashtable will be empty.

3.   Fill in the method insert of ZipcodeHashtable class. [10 pts]

a.    Use hashCode method of Zipcode object to identify which bucket the object should be placed in.

b.   Use Separate Chaining as a collision resolution mechanism (i.e., when more than one object returns the same hash code, add the object to the Linked List).

c.    size variable must be adjusted accordingly.