FHTW Berlin Fachbereich 4 Internationaler Studiengang Internationale Medieninformatik (Bachelor) Info 2: Informatik II Winter Term 2007/08

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. Review the construction of a hash function. Note that you will need prime numbers. Does your isPrime method work? If not, fix it now.
5. 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!
6. Given a selection of n pizza toppings - how can you generate a list of all of the different k-toppings where k<n? Hint: Look at the binomial coefficient. Write a method that takes a String of n characters and returns an array of k-character Strings that are all characters in the original string.

There is a lot to be done here, so have one person focus on making the hash function while the other sets up the data structure. Whoever is done first gets the lookup method sorted out. Make the basic cheater together, and then split up with one person perfecting the cheater interface for all shorter words and the other creating all the Strings containing only letters that are in the original 7 letters.

1. Write a dictionary class that upon instantiation reads in a file of words and creates a hash table for storing them. Use chaining of collisions. How many entries does your table have? How many collisions were there? What is the longest chain in your hash table? Some statistical methods might be nice. Can you fix your hash function to have chains of 16 or less?
2. (For the bored) Can you make a perfect hash? Describe how you went about finding a perfect hash for an extra star.
3. 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.
4. Now make the basic Scrabble cheater - set up 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.
5. (For the bored) Write a method bool isPermutation (String a, String b) {...} so that only permutations are printed out.
6. Make a class that upon instantiation with a given String of characters, determines all of the Strings that are substrings in the sense that they only contain letters from the given String, with multiples only up to the number of multiples available. The order of the letters is irrelevant, so this is a bag. For example with 4 letters "JAVA" this would be {"AAJV", "AJV", "AAJ", "AAV", "AA", "AJ", "AV", "JV"}. Don't worry about single letters. Your finger exercise will come in handy here.
7. Now set up the Scrabble Cheater DeLuxe: read in 7 letters, split them into collections of 7-, then 6-, then 5-, ... words contained in the input bag of letters. Look up each word in each collection in the corresponding dictionary. If you find something, output it.
8. (For the bored) Collect up all the words which are only permutations of the looked up word, and sort them all, irrespective of length, alphabetically, before outputting them. Have alternate output alphabetically by length.
9. (For really bored people during vacation time: Check out http://www.morewords.com and see that you can use wild cards such as "-" for matching any one character and "*" for matching any string. Can you replicate this (even if it is much slower than morewords).  

Now look back to Java Eyes and the Spirograph - it has been a hard year. Did you learn to program? Sure you did! You are not perfect yet, but keep practicing! Have a good break!

This exercise is due for everyone on February 6, 2008!