Problem Set 6. Posted 2/23

1. Write a java program that reads a text file (for example, one of the novels made available for Project 1) and changes all occurances of the word "red" to the word "blue." Note that "red" should be changed to "blue" only when "red" occurs as a word. For example, if "credentials" occured as a word in the input file, you would not change "credentials" to "cblueentials." Use the definition of a word, as given in the description of Project 1. Prompt the user for the name of a text file to read from. If the name of the input text file is "foo," write the output to a file called "foo.out."

2. Write an efficient implementation of a function that calculates the hash value of a given string of lower case letters. Use the formula given in Project 1 handout. Use the two tricks given in pages 564-565: taking repeated remainders to avoid overflow and using Horner's method to decrease the number of multiplications and additions. There is one more trick mentioned at the bottom of page 565. This is to replace multiplications by the bit shifting.

   Here is a more detailed description of this trick. Multiplying an integer by 2 is the same as shifting the bits of the number to the left by 1 and making the rightmost bit 0. For example, 0000 0111 is the 8-bit binary representation for 7 and 0000 1110 is the 8-bit binary representation for 14. This means that multiplying a number by 2^k is equivalent to doing a left shift on the bits of the number k times. For example, multiplying a number by 32 would be equivalent to doing a left shift 5 times. Instead of thinking of each letter in the string as a base-26 digit, think of it as a base-32 digit. Then, in the formula for the hash function, we would need to multiply by 32 rather than by 36. Multiplying by 32 can be done by simply doing a left shift by 5. If you need to learn more about bit shifting operations go here.