HTW Berlin Fachbereich 4 Internationaler Bachelor Studiengang Internationale Medieninformatik (Bachelor) Info 2: Informatik II Summer Term 2023

Finger exercises
 

1. Review the rules of Scrabble, if you have never played it before.
2. What would the exact data structure be for a hash table that stores Strings and chains the collisions?
3. What would a normalization function for words look like for a hash? That is, "JAVA" and "VAJA" are permutations, what would a normalized permutation look like?
4. How do you determine if two strings are permutations of each other?
5. Review the construction of a hash function. Note that you will need prime numbers. Does your isPrime method work? If not, fix it now.
6. Can you find lists of valid words for Scrabble in English online? Are there perhaps any sorted by number of letters in the word? Or maybe one file for each word size? Note down the URLs!

1. Write a dictionary class that upon instantiation reads in a file of words and creates a hash table for storing them. Do not use the Hashtable class from Java, but make your own! Use chaining of collisions in your hash table. Your table should be smaller than the number of words that you are storing in it. Let's see some statistics, it might be useful to implement some statistical methods in order to see if your hash table is "okay" :
   1. How many entries does your table have?
   2. How many collisions were there?
   3. What is the longest chain in your hash table?
   4. Can you fix your hash function in order to only have chains of 16 or less? What did you have to do?
2. You will need to have a lookup method in your class that takes a word (i.e. a String) and returns an array of Strings corresponding to all the words at the hash location, if any. You may need to normalize the word to look up, depending on your hash function.
3. Now make the basic Scrabble cheater: construct a 7-letter-word hash dictionary, set a String to 7 letters, and output the array of Strings found that might be permutations of these 7 letters. Your users can check if there is a permutation to be found. Or you can implement isPermutation and only output the ones that are permutations if you are bored.
4. (For the bored) Can you make a perfect hash? Describe how you went about finding a perfect hash!