Compsci 100, Spring 2009, March 6 Recitation

name: __________________________   login: _____________

name: __________________________   login: _____________

name: __________________________   login: _____________

See Also Tree Questions

The output below shows both the time it takes to create the same map using two different methods and then several shortest word ladders between two words where the ladders are found using the map. You'll reason about the methods used to created maps and find ladders and you'll write code on paper to solve problems related to the word ladders. The code is from the class WordLadders.java used in this lab; formatted printed copy is accessible.

In the map, each 5-letter word (the 5 is a constant at the top of the class) is a possible key in the map created. The value associated with each key is a list of words that are one-away from the key. For example, if the key is "steep", the value is the list below:

   sheep, sleep, steed, steel, steer, strep, sweep

# words read = 5757
map A time = 1.206000 for map with 28270 entries
map B time = 0.117000 for map with 28270 entries
1	clock
2	block
3	blocs
4	blots
5	boots
6	bouts
7	pouts
8	pours
9	hours
-------------
1	loves
2	laves
3	haves
4	hates
-------------
1	rifle
2	rille
3	rills
4	rials
5	reals
6	rears
7	sears
8	scars
9	scare
10	sware
11	sward
12	sword
-------------

1. These questions are about the code in method createMapA which is shown below.

   1. In terms of both L, the length of the words being considered and N, the number of L-length words describe the complexity of the method createMapA from the code which is reproduced below. Use big-Oh to develop an expression that uses both L and N and provide a justification for your answer.

   2. Why are there two calls to map.put within the body of the inner loop?

   public class WordLadders { private ArrayList<String> myWords; private Map<String, ArrayList<String>> myMap; private static int WORD_SIZE = 5; /** * Return true iff a and b differ by only one letter * @param a is a String of n letters * @param b is a String of n letters * @return true if and only if a and b share n-1 letters in the same position */ private boolean oneApart(String a, String b){ int count = 0; for(int k=0; k < a.length(); k++){ if (a.charAt(k) == b.charAt(k)) { count++; } } return count == a.length()-1; } /** * Create a map in which every word is a key and the value is the * list of words one away from the key. * @return a String describing the map created */ public String createMapA(){ myMap.clear(); double start = System.currentTimeMillis(); int count = 0; for(int k=0; k < myWords.size(); k++){ String kword = myWords.get(k); for(int j=k+1; j < myWords.size(); j++){ String jword = myWords.get(j); if (oneApart(jword,kword)){ ArrayList<String> list = myMap.get(jword); if (list == null){ list = new ArrayList<String>(); myMap.put(jword,list); } list.add(kword); list = myMap.get(kword); if (list == null){ list = new ArrayList<String>(); myMap.put(kword,list); } list.add(jword); count += 2; } } } double end = System.currentTimeMillis(); return String.format("time = %f for map with %d entries", (end-start)/1000.0, count); }

2. These questions are about the code in createMapB.
   1. Develop and justify an expression for the other method for creating maps, the createMapB method. You'll need to look at the code in the StringSub class since several of it's methods are used. However, in general the methods of that class are either O(1) or O(L) for L-length words. Although the code for createMapB contains a loop from ['a'..'z'] the number of characters looped-over, 26, is considered a constant with respect to L and N here.

   2. The line below guards the code that puts an element in the list associated with the key s in the map. Explain the purpose of both parts of the boolean && below. if ((!word.equals(copy)) && set.contains(word))
   3. What is the purpose of the char value saved that is used before the loop that goes from 'a' to 'z'?

   /** * Create a map in which every word is a key and the value is the * list of words one away from the key. * @return a String describing the map created */ public String createMapB(){ myMap.clear(); double start = System.currentTimeMillis(); Set<StringSub> set = new HashSet<StringSub>(); for(String s : myWords){ set.add(new StringSub(s)); } int count = 0; StringSub word = new StringSub("xxxxx"); StringSub copy = new StringSub("xxxxx"); for(String s : myWords){ ArrayList<String> list = new ArrayList<String>(); myMap.put(s,list); word.replace(s); copy.replace(s); for(int k=0; k < WORD_SIZE; k++){ char saved = word.getChar(k); for(char ch = 'a'; ch <= 'z'; ch++){ word.setCharAt(k, ch); if ((!word.equals(copy)) && set.contains(word)){ String ns = word.toString(); list.add(ns); count += 1; } } word.setCharAt(k, saved); } } double end = System.currentTimeMillis(); return String.format("time = %f for map with %d entries", (end-start)/1000.0, count); }

3. In the code that finds word ladders in method ladder the starting word is put on a queue. Then whenever a word current is removed from the queue, every word w one-away from the removed word is enqueued as long as w has not been previously enqueued. The code is shown below -- questions follow the code.
   public int ladder(String start, String end) { Queue<String> q = new LinkedList<String>(); Map<String,String> from = new HashMap<String,String>(); q.add(start); from.put(start, null); OUT: while (q.size() != 0){ String current = q.remove(); for(String s : myMap.get(current)){ if (s.equals(end)){ from.put(end, current); break OUT; } if (! from.keySet().contains(s)){ q.add(s); from.put(s, current); } } } String s = end; int count = 1; while (from.get(s) != null){ System.out.println(count+"\t"+s); s = from.get(s); count++; } System.out.println(count+"\t"+s); System.out.println("-------------"); return count; }
   1. Explain why every word one-away from start is put on the queue before any word that is two-away from start.

   2. Every word enqueued via q.add(s) is also made a key in the map from in the code. Explain how this prevents words from being enqueued more than once (refer to the code as needed.)

   3. The label OUT before the while loop is a target for the labeled-break statement break OUT which causes control-flow to continue after the while loop. Explain why the break OUT is used in the code.

   4. The map from is used to re-create the word ladder -- any word put on the queue is a key in the map with the associated value the word one-away that caused the key to be put on the queue. Explain why this results in printing the word-ladder backwards, e.g., when start is "hours", that word is printed last in the word ladder (see the output above).

4. On the computer from which the timings above are taken the average time to find a word ladder (or that there is no word ladder) is 0.005 seconds -- five-thousandths of a second. Note that there are 5757 five-letter words (see the output). Suppose you write code to find the longest word ladder by trying every possible pair of words and tracking which of the resulting word ladders is longest as below. public int longestLadderLength(){ int max = 0; for(int k=0; k < myWords.size(); k++){ String kword = myWords.get(k); for(int j=k+1; j < myWords.size(); j++){ int len = ladder(myWords.get(j), kword); max = Math.max(len,max); } } return max; }
   1. Why is it ok for the inner loop to start at k+1 instead of at zero?

   2. Develop and justify an estimate as to how long the code will take to find the longest ladder between 5-letter words.