Priority Queues



COP 3538 – Data Structures with OOP

Project 5 – Fall 2013

Due: Monday, December 1st, 2013 .

Hashing

Using NetBeans 7.1, you are to write a Java program using OOP principles to accommodate the following functionality

Assignment #5

Objectives:

Provide student with exercises in learning UML

Provide student with exercises in Javadoc and its various formats

Provide student with hashing and collision algorithms and other practical p programming exercises

Task 1: Build the Hash Table. You are to build the hash table in the order of appearance of the records (Strings) in the sequential input data file. Using Heaps.States.Fall2013.txt file, you are to build a hash table using the state names (converted to numeric values to be discussed in class ) mod 29, size of hash table.

You are to use the hashing of strings algorithm (see book and lecture notes part 2 for the algorithm) as your hashing function. You are to use separate chaining as your collision algorithm (see also textbook and my lecture notes).

Task 2: Display Hash Table: Once the hash table is built from the input constrained by the hashing and collision algorithms cited above, display the hash table with all its entries and any synonyms, as appropriate. Your format – always include nice headers, etc. – should appear in tabular format: hash table index in the left most column starting with 0 followed by, say, five spaces, followed by the statename stored in this home address, followed by any synonyms appearing to the right. Any items linked to this home address are to appear left justified (lined up in column fashion) to the right of this first entry, with spaces in between any succeeding collision at that hash table address. All these columns are to be left justified and aligned. If a hash table entry has no entries, the place normally occupied by an entry will be empty. The table index to the left will still be present, however.

Task 3: Update the Hash Table: Using the Heaps.Update.Fall2013.txt, you are to update your hash table. You are to use the same hashing and collision algorithms as you used to originally build the hash table. There are Add transactions and Delete transactions (see file). Additions: Add statenames to the Hash Table. Deletions: These are to be flagged with a delete byte. Items are to be logically deleted and not physically deleted. There are no invalid deletes or dupe adds.

Task 4: Display Updated Hash Table: Using the format described above, you are to display the updated hash table and its links. For those records that are logically deleted, but still physically present, you are to precede the nickname with an asterisk, as in: *Delaware.

Grading: Please note that this program is worth 70 points because it is short and no design documentation is required. Start early, and you will have no problems as usual.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download