Recitation 9: Tries and Boggle

March 22, 2013

All answers should be submitted using this submission form.

Part 1: Tries

The picture below shows a trie representing the words "dog", "dot", "doting", "drag", "drastic", "top", "torn", and "trap". Tries are used in Boggle Assignment in TrieLexicon.java.

The trie supports queries (add, contains, delete) in O(w) time for a word with w-characters. This is independent of the number of words in the trie. Each node has a subtrie/child if there is a word starting with the letter labeling the branch out of the trie-node. For example, adding "dust" to the trie below would cause a "u"-node to be added as a new child of the "d"-node that already has two children, "o", and "r". The code to add a node and to determine if a string is a word or prefix is below the diagrammed trie (You can find this code in TrieLexicon.java)

public boolean add(String s) { Node t = myRoot; for (int k = 0; k < s.length(); k++) { char ch = s.charAt(k); Node child = t.children.get(ch); if (child == null) { child = new Node(ch, t); t.children.put(ch,child); } t = child; } if (!t.isWord) { t.isWord = true; // mark as word mySize++; return true; } return false; // already in set } public LexStatus wordStatus(StringBuilder s){ Node t = myRoot; for (int k = 0; k < s.length(); k++) { char ch = s.charAt(k); t = t.children.get(ch); if (t == null) return LexStatus.NOT_WORD; } return t.isWord ? LexStatus.WORD : LexStatus.PREFIX; }

1. Explain in words why searching for a word or adding a word of w-characters is an O(w) operation for a word of w-characters and not an O(n) operation for a lexicion with n-words.

2. The definition of the Node class in the Trie is below. The map children stores references to all the children of a node. Provide a reason as to why a map is used rather than an array of 52 characters (such an array would allow for upper and lower case characters).
   public static class Node { String info; boolean isWord; Map<Character,Node> children; Node parent; Node(char ch, Node p) { info = ""+ch; isWord = false; children = new TreeMap<Character,Node>(); parent = p; } }

3. Write a method that returns a copy of the entire trie rooted at a node. Trie nodes have parent pointers, though they're not shown in the diagram above. The second parameter to a Trie-Node constructor is the node's parent. private Node copyTrie(Node root){ if (root == null) return null; Node copy = new Node(root.info.charAt(0),null); copy.isWord = root.isWord; // now copy children of root and then set all // the copied children's parents pointers to 'copy' return copy; }
4. Write a method to traverse all nodes in a trie and return the number of words in the trie, by referencing the isWord field of each node. private int wordCount(Node root){ if (root == null) return 0; }
5. Discuss at a high level how to collapse chains of nodes with single pointers in a trie into one node with a longer string labeling it. For example, the diagram above would be collapsed into the trie shown below. In your brief discussion remember that the nodes have parent pointers. For example, if you get to a leaf in a trie, how do you "back up" to a node that can represent more than one character as shown below? When does that "back up" process stop?
   
   
   
   Compressed tire
   
   
   

   Part 2: Boggle

   
   
   Here's code from a GoodWordOnBoardFinder implementation. The code uses a helper method, as indicated in the Boggle Howto to find where a word occurs on a boggle board.
   public List<BoardCell> cellsForWord(BoggleBoard board, String word) { ArrayList<BoardCell> list = new ArrayList<BoardCell>(); for (int r = 0; r < board.size(); r++) { for (int c = 0; c < board.size(); c++) { if (findHelper(word, 0, r, c, board,list)) { return list; } } } list.clear(); return list; } Here's the header for the private helper method. /** * Returns true if and only if the substring of word starting at * index can be formed starting at (row,col) on the board provided * without using any cells stored in list --- and extending list * to include all cells on which substring is found when true is * returned. * @param word is searched for word (e.g., entered by user) * @param index is where in word substring starts, e.g., all chars * before index have been found and cells are in list * @param row is starting point for search * @param col is starting point for search * @param board is board on which word is searched * @param list is cells on board where word is found * @return true if substring found on board without re-using board-cells */ private boolean findHelper(String word, int index, int row, int col, BoggleBoard board, List<BoardCell> list) { }
   1. If there's no substring, e.g., index is past the end of the string, what value should the method return and why? Write the code for this check.

   2. If either row or col is outside the board what value should be returned and why? Write the code for this check.

   3. The call board.getFace(row,col) returns the string on the corresponding board-cube. Use this call to determine if the first letter of the substring starting at index matches the board cell. Write code.

   4. If the boardcell matches the first character, you'll need to check whether the boardcell has been used, i.e., appears in list. Write code using list.contains to check. You'll have to create a BoardCell object from (row,col).

   5. How many recursive calls are made to check whether the substring can be formed? What's the value of index for each recursive call, based on the value of index passed in? How is the value of parameter list in the recursive calls different from the value passed into the function making the recursive calls?

   6. If the recursive calls all fail the method must return false, but what code will you write to ensure that the value of list is the same as it was when the method was first called.