here is the "sample.txt" :

An Inkjet printer is a printer for computers. It uses special ink to print on the paper. Another type of printing technology is the Laser printer. Inkjet printers are preferred for printing photos and graphics due to their high quality color output, whereas laser printers are preferred for printing text due to their high contrast and speed. Usually, inkjet printers are used by people who print very little. The ink comes in special ink cartridges, which can be very expensive and uneconomical. Also, the ink in the cartridge may dry up. This means that a new cartridge is needed. Three colors of cartridges, which combine magenta, yellow and cyan inks are used to create color tones. A black cartridge is also used for crisp monochrome output. Some professional printers have one or more additional colors for better photo quality, such as light cyan, light magenta, blue, red, green, orange, and grey. Inkjet printers may use either dye or pigment inks. Pigment inks are less likely to fade, whereas dye inks create more realistic photos and are less likely to clog the printhead. Many professionals use inkjet printers to print on very large surfaces. These printers usually do not use cartridges, but have a continuous supply of ink that could last for a long time. Standard size printers with a continuous ink supply are also available. Inkjet printers need special paper. This paper has been treated so that the ink does not smear. Less expensive inkjet printers are a bargain for users who want to be able to print pages in color. Inkjet printers can be very cheap but the ink can also be rather expensive. Some professional inkjet printers can print on surfaces other than paper, such as CDs, DVDs or plastic cards.  

The following are some of the steps that should be taken to solve the question. Please note>>

1. Find all unique alphabetical words in the text file and store them in a collection (e.g. array or arraylist)

For your reference, the following is a sorted, partial list of unique words:

[a, able, additional, also, an, and, another, are, as, available, bargain, be, been, better, black, blue, but, by, can, cards, cartridge, cartridges, cds, cheap, clog, color, colors, combine, comes, computers, continuous, contrast, could, create, crisp, cyan, do, does, dry, due, dvds, dye, either, expensive, fade, for, graphics, green, grey, has, have, high, in, ink, inkjet, inks, is, it, large, laser, … who, with, yellow]

2. Create two different hash tables both with hash functions (a) and (b) and for each load factor. This makes for a total of 40 hash tables. At this stage, ignore hash function (c) as it has some indexing issues. You may use a simple array for this purpose. Since no deletion is involved, the flags EMPTY, OCCUPIED and DELETED are also not needed.

Assuming that you have two hundred unique words, the size of the hash table with load factor

0.05 will be 200/0.05 = 4000.

0.10 will be 200/0.10 = 2000.

0.15 will be 200/0.15 = 1333.33 = 1334 (rounded up)

…

0.95 will be 200/0.95 = 210.52 = 211.

3. Now do a search for ALL of the unique words in the two hash tables. Use the same hash function as used for creating the hash table. If there’s a collision do linear probing (i.e. increase the search index by 1). In the end count the TOTAL number of collisions and DIVIDE by the input size to give the AVERAGE number of collisions.

4. You will observe the following trends.

As the load factor increases, the average number of collisions should increase (in general) [But it might decrease in 1 or 2 places which is ok].

For the 2^nd hash function [Cichelli], the average number of collisions should be much higher than the first.

Submission Details:

1. Please submit your java program with the main method (a single file is STRONGLY PREFERRED).
2. Please submit a text file with the average number of collisions. This should be the output of your program. [You may print the output only and then save and submit this separately as a text file]. The format of the text file should be as follows:

Hash Function 1: [PLEASE NOTE>> YOU MAY NOT GET THE SAME VALUES]

[ASCII value of] First Letter + [ASCII value of] Second Letter + … + [ASCII value of] last letter

LOAD FACTOR AVERAGE NUMBER OF COLLISIONS

0.05 0.707

….

0. 7.314

Hash Function 2: [PLEASE NOTE>> YOU MAY NOT GET THE SAME VALUES]

[ASCII value of] First Letter + [ASCII value of] Second Letter + … + [ASCII value of] last letter

LOAD FACTOR AVERAGE NUMBER OF COLLISIONS

0.05 47.05

….

1.00 47.07

Transcribed Image Text:

[Submit a java program. The text file is "sample.txt" with this homework] As discussed in this chapter, the linear probing technique used for collision resolution has a rapidly deteriorating performance if a relatively small percentage of the cells are available. This problem can be solved using another technique for resolving collisions, and also by finding a better hash function, ideally, a perfect hash function. Write a program that evaluates the efficiency of various hashing functions combined with the linear probing method. Have your program write a table similar to the one in Table 10.1, which gives the averages for successful and unsuccessful trials of locating items in the table. Use string methods and a large text file whose words will be hashed to the table. Here are some examples of hash functions (all values are divided modulo TSize): a. FirstLetter(s) + SecondLetter(s) + + LastLetter(s) b. FirstLetter(s) + LastLetter(s) + length(s) (Cichelli) C. for (i = 0, index = 0; is.length; i++) index = (26 index + s.charAt(i) - '); (Ramakrishna) " [Submit a java program. The text file is "sample.txt" with this homework] As discussed in this chapter, the linear probing technique used for collision resolution has a rapidly deteriorating performance if a relatively small percentage of the cells are available. This problem can be solved using another technique for resolving collisions, and also by finding a better hash function, ideally, a perfect hash function. Write a program that evaluates the efficiency of various hashing functions combined with the linear probing method. Have your program write a table similar to the one in Table 10.1, which gives the averages for successful and unsuccessful trials of locating items in the table. Use string methods and a large text file whose words will be hashed to the table. Here are some examples of hash functions (all values are divided modulo TSize): a. FirstLetter(s) + SecondLetter(s) + + LastLetter(s) b. FirstLetter(s) + LastLetter(s) + length(s) (Cichelli) C. for (i = 0, index = 0; is.length; i++) index = (26 index + s.charAt(i) - '); (Ramakrishna) "