This homework asks you to design and implement a class called wordCollection that maintains a collection of String objects and supports the operations insert, search, and delete on this collection. I would like the collection of String objects to be maintained in a 2-dimensional array as follows. Let M be the number of rows in the 2-dimensional array. For a given string s, compute an index by adding up the ASCII values of the characters in s and then taking the remainder with respect to M. This will give, for each string s, an index in the range [0, M-1]; let us denote this index h(s). The main idea is to store string s in row h(s). To search for a given string s, we compute h(s) and then perform a linear scan of the row to find s. The delete is similar to search, except that at the end s has to be deleted from the row h(s).

1. What data members should this class have?

   What to submit: Well-documented Java code fragment showing names and types of data members. The comments should clearly describe the purpose of each data member.

2. Implement the following two constructors for the class:

   	public wordCollection()
   	public wordCollection(int M)
   

   The user calls the default constructor when she does not know (or does not care) how many strings she expects to store. In this case, the programmer has to decide how many rows to allocate. The user calls the second constructor above, with argument M when she knows that she would like to be allocated M rows.

   Despite what I have specified here, there are still several choices you need to make. For example, how large should you initially make each of the rows, etc. Your code will be judged on the quality of and justification for these choices.

   What to submit: Submit Version 1 of the wordCollection class, with just the data members and constructors. Call this file wordCollection1.java. Your code should compile and you should make sure that your code is well-documented.

3. Implement the insert method. The function header for this method should be:

   	public void insert(String s)
   

   This method should take care of the possibility that row h(s) may be full, by expanding rows when needed. Note that the number of rows does not change over the lifetime of the wordCollection object.

   What to submit: Submit Version 2 of the wordCollection class, with just the data members, constructors, and the insert method. Call this file wordCollection2.java. Your code should compile and you should make sure that your code is well-documented.

4. Let us test your insert method with the 5-letter words in the file words.dat. Write a program, called wordCollectionTester1 that starts by constructing a wordCollection object with 500 rows and then reads each of the words from words.dat and inserts these into the wordCollection object. To make sure that the words were inserted correctly, add a method called printAll to the wordCollection class. printAll is a 0-argument method that scans each row of the wordCollection object and prints out the strings. printAll should format the output in a way that is easy to read. Here is one example format, you could use. In this example, Row 0 contains 12 words and these appear after the label "Row 0," ten words per line. Row 1 is empty and Row 2 contains 30 words, etc.

   Row 0
   word1	word2	word3	...	word10
   word11  word12
   Row 1
   EMPTY
   Row 2
   word1	word2	word3	...	word10
   word11	word12	word13	...	word20
   word21	word22	word23	...	word30
   Row 3
   word1 word2
   ....
   ....
   

   In your program wordCollectionTester1, you should call the printAll method after you have inserted all the words.

   What to submit: Submit Version 3 of the wordCollection class. This should contain everything that Version 2 contained and additionally the printAll() method. Call this file wordCollection3.java. Your code should compile and you should make sure that your code is well-documented. Also submit wordCollectionTester1.java and the output obtained from executing wordCollectionTester1.java.

5. The algorithm to search a wordCollection object for a given string s is fairly straightforward. First we compute the index h(s) and then we perform a linear search on the row with index h(s). The search method would be most efficient if all of the rows had "small" size. In particular, for the example of 5-letter words, if the 5757 words were evenly distributed in the 500 slots of the wordCollection object, we would see about 11-12 words per row - not too many to perform a linear search on. From this discussion it should be clear that the distribution of the words into the rows of the wordCollection object plays a critical role in determining the efficiency of search (and delete). Implement a method of the wordCollection class, called printFrequency that reports on the lengths of the rows in the wordCollection object as follows:

   	[0, 49]: n1
   	[50, 99]: n2
   	[100, 149]: n3
   	....
   	....
   

   Here n1 is the number of rows whose length is between 0 and 49 (inclusive), n2 is the number of rows whose length is between 50 and 99 (inclusive), etc.

   Modify your program wordCollectionTester1, so that after the words in words.dat are inserted into the wordCollection object, it calls the printFrequency method. Call this new program wordCollectionTester2.

   What to submit: Submit Version 4 of the wordCollection class. This should contain everything that Version 3 contained and additionally the printFrequency() method. Call this file wordCollection4.java. Your code should compile and you should make sure that your code is well-documented. Also submit wordCollectionTester2.java and the output obtained from executing wordCollectionTester2.java.