Problem Set 8. Posted 3/23

Notes: Of the three problems given below, one will be solved by the TAs in next week's discussion section, you will have to solve one in class, and the remaining problem is due in the lecture on Friday, 3/31.

1. Write the following functions:
   • A function called missingLetter that takes a String called word and returns a String array containing all strings that can be obtained by deleting one character from word. For example, if dog is the given string, then the function should return an array containing og, dg, and do (not necessarily in this order).
   • A function called extraLetter that takes a String called word and returns a String array containing all strings that can be obtained by adding one letter to word. The new letter can be inserted at any position in word. Only add lower case letters. For example, if dog is the given string, then the function should return an array containing adog, daog, doag, doga, and then words obtained by inserting the letter "b" in all positions, then the letter "c" and so on.
   • A function called substitutedLetter that takes a String called word and returns a String array containing all strings that can be obtained by substituting one character in word by a letter. The substitution can occur at any position in word. Only use lower case letters for substitution. For example, if dog is the given string, then the function should return an array containing aog, dag, doa and then words obtained by substituting "b" for each of the letters in dog, and then the letter "c" and so on.
   • A function called swappedLetter that takes a String called word and returns a String array containing all strings that can be obtained by swapping two adjacent characters in word. For example, if dog is the given string, then the function should return an array containing odg and dgo.

2. Write a function called replacements that takes a string called word and returns an array containing all strings that are at most two hops away from word in the graph of strings defined in Project 2. You can assume that word only contains lower case letters.

   Note that in this problem, there is no "dictionary" and therefore there is no notion of correctly spelled words and incorrectly spelled words.

   Here is a high level description of the algorithm you might want to use to solve this problem:

   1. Call each of the 4 functions, missingLetter, extraLetter, substitutedLetter, and swappedLetter and suppose that the String arrays returned by the functions are S1, S2, S3, and S4. Together, these arrays contain all strings that are 1 hop away from word.
   2. Now we need to obtain strings that are 2 hops away from word. Put the strings in S1, S2, S3, and S4 into a single string array S. For each string x in S, do the following two steps:
      1. Call each of the 4 functions missingLetter, extraLetter, substitutedLetter, and swappedLetter with x as the parameter. Again, suppose that the String arrays returned by the functions are S1, S2, S3, and S4.
      2. Append the contents of S1, S2, S3, and S4 into a string array called L.
      After the loop has executed for all strings in S, the array L will contain all strings that are 2 hops away from word. Note that L may also contain words that are 1 hop away and it will even contain word itself.

3. This problem is on the sorting algorithms, merge sort and quick sort, discussed in class this week (3/20-3/24). First consider recursiveMergeSort. Let us suppose that we insert an output statement immediately after each of the two calls to recursiveMergeSort. The output statement is meant to print out the entire array that is being sorted. Write down the output you would see when you call recursiveMergeSort with the following 6 element array:

   	8     3     11     2     1     25.
   

   Make sure that the lines of output appear in the correct order.

   Solve exactly the same problem for recursiveQuickSort.