Week 10 Tutorial Questions

Heaps

1. Using the heap-as-array data structure from lectures, show how an initially empty max heap changes when the following values are inserted.

   S  O  R  T  I  N  G  I  S  F  U  N
   

   At each step, show how the fixUp() function is used.

2. Consider the series of heap operations below. Assuming that higher values have higher priority, show the state of the heap (in both binary tree form and array form) after each operation.

   Heap h;
   Item it;
   h = heapNew();
   
   heapInsert(h, 10);
   heapInsert(h,  5);
   heapInsert(h, 15);
   heapInsert(h , 3);
   heapInsert(h, 16);
   heapInsert(h, 13);
   heapInsert(h,  6);
   it = heapDelete(h);
   heapInsert(h,  2);
   it = heapDelete(h);
   it = heapDelete(h);
   it = heapDelete(h);
   it = heapDelete(h);
   it = heapDelete(h);
   

Tries

1. Consider the following trie:

   

   Show which nodes would be visited when searching for each of the following words:

   1. now
   2. the
   3. ant
   4. access
   5. actor
   6. action
   7. actors
   8. tang
   9. a

2. Under what circumstances would inserting a new word into a trie not result in adding any new nodes? What would be the effect on the tree of inserting the word?

3. Show the final trie resulting from inserting the following words into an initially empty trie.

   so   boo   jaws   boon   boot   axe   jaw   boots   sore
   

   Does the order that the words are inserted affect the shape of the tree?

4. What are the two cases when deleting a word from a trie? How is each case handled?

5. Autocomplete is a feature in which an application predicts the rest of a word a user is typing. For example, if a user has typed in "th", then autocomplete may suggest the words "the", "they", "then", and so on.

   1. Explain how a trie could be used to implement basic autocomplete, which suggests all possible words.
   2. Users are much more likely to type some words than others, so ideally autocomplete should suggest more likely words. For example, if a user has typed "tho", autocomplete should suggest "though" instead of "thou". How could you extend your solution so that autocomplete suggests more likely words?