Week 10 Tutorial Questions

Heaps

1. 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);
   

2. Suppose you are given an array \(A\) of size \(n\), and you would like to find the largest \(k\) elements (\(k \le n\)). For example, if given the array \(A = [7, 4, 2, 5, 9]\) and the value \(k = 3\), the largest \(k\) values are 9, 7 and 5.

   1. A simple way to solve this problem is to sort the array in increasing order, and then the largest \(k\) elements would be the last \(k\) elements of the sorted array. What is the worst-case time complexity of this approach?
   2. Come up with a more efficient method that uses a heap. What is the worst-case time complexity of this method?

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?

6. It's the year 2521, and space exploration has uncovered an alien language (which just so happens to use the same letters as English 😉️)! A team of linguists has found that these aliens loved poetry, and that two words are said to rhyme with degree \(k\) if the last \(k\) letters of each word are identical. For example, the words GOODRA and QUOLODRA rhyme with degree 4, as the last 4 letters of these words are identical. These words also rhyme with degree 1, 2 and 3.

   To help investigate this poetry and write some of your own, you would like to devise a method to find the number of words that rhyme with a given word with degree \(k\).

   For example, suppose the words of the language are ARON, AGGRON, SQUARON, RONA, LAVARON and UDON. Then:

   • The number of words that rhyme with SQUARON with degree 2 is 4 (the words are ARON, AGGRON, LAVARON and UDON)
   • The number of words that rhyme with SQUARON with degree 3 is 3 (the words are ARON, AGGRON and LAVARON)
   • The number of words that rhyme with SQUARON with degree 4 is 2 (the words are ARON and LAVARON)
   • The number of words that rhyme with SQUARON with degree 5 is 0.

   Can you come up with a method to efficiently answer queries like the ones above? Suppose you are allowed to preprocess the words of the language before answering any queries.