# 5.4. Homework ## Auto-Complete Most virtual keyboards provide the option of auto-complete, which gives a list of candidate words that you wish to type given a prefix you enter. For instance, when you type "sh", it gives a list of candidate words such as "she", "shell", "ship", etc. ``` "sh" -> ["she", "ship", "shell, ...] ``` If you select a word from the candidates, it should learn your selection as the top candidate for that prefix. For instance, if you select "ship" from the example above, the next time you enter the same prefix "sh", it should give a list of candidates where the first item is "ship" instead of "she". ``` "sh" -> ["ship", "she", "shell, ...] ``` Your task is to write a program that gives a list of candidate words for any prefix and learns the selected candidates. ## Tasks * Create a class called [`AutocompleteHW`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/trie/autocomplete/AutocompleteHW.java) under the [`autocomplete`](https://github.com/emory-courses/dsa-java/tree/master/src/main/java/edu/emory/cs/trie/autocomplete) package: * This class extends the abstract class [`Autocomplete`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/trie/autocomplete/Autocomplete.java), which extends [`Trie`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/trie/Trie.java). * The value type of the generic `T` can be a collection of strings (e.g., `List`). * You must create a constructor that takes two parameters, `dict_file` and `max`, and calls its [super constructor](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/trie/autocomplete/Autocomplete.java#L36), which reads all words in the dictionary file (e.g., [`dict.txt`](https://github.com/emory-courses/dsa-java/blob/master/src/main/resources/dict.txt)). * Override the `getCandidates()` method that takes a prefix and returns a list of candidate words matching the prefix: * The max-number of candidates in the list must be the return value of the `getMax()` method. * The most recently selected candidate should appear as the 1st item, the 2nd most recently selected candidate should appear as the 2nd item, and so on. * The rest of the candidate list should be filled with the shortest words matching the prefix. * If there are more than one candidate with the same lengths, they should be sorted alphabetically. * Make sure the same candidate does not appear more than once. * Override the `pickCandidate()` method that takes a prefix and a selected candidate, and saves the information: * This is the most recently selected candidate for that particular prefix. It must appear as the first item in the candidate list when the same prefix is entered next time. * Submit `AutocompleteHW.java` to Canvas. ## Extra credit * Create a class called [`AutocompleteHWExtra`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/trie/autocomplete/AutocompleteHWExtra.java) under the [`autocomplete`](https://github.com/emory-courses/dsa-java/tree/master/src/main/java/edu/emory/cs/trie/autocomplete) package. * Feel free to change the generic type, representing the value type of each `TrieNode`, to anything other than `List` (`List`). * The `getCandidates()` method: * Must show the most frequently picked candidate first, the 2nd-most frequently picked candidate next, and so on. * If there are more than one candidate with the same frequency, sort them by recency. * The rest of candidates should be filled as in the original task. * You must submit both `AutocompleteHW` and `AutocompleteHWExtra` to earn the extra credit. ## Notes * Do not change the dictionary file. If you find anything peculiar about the dictionary file, please let me know so everyone works on the same copy of the dictionary file. * Please test your program yourself. We will evaluate your program using our unit tests and measure the performance (both speed and accuracy). * Take a look at [Map](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Map.html) if you are not familiar with methods in the standard library. * If you are having trouble with implementing `getCandidates()`, think about how to traverse the trie given any node. * If you are having trouble with implementing `pickCandidate()`, take a look at [`Trie#put`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/trie/Trie.java#L54). * You are not allowed to use any type of [Map](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Map.html) to store candidates for this homework. * Your program should be able to handle prefixes or candidates that do not exist in the dictionary. * All picked candidates should be introduced as real words to the trie. * Whitespaces are not allowed as input; thus, you should trim all input strings. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://emory.gitbook.io/dsa-java/tries/homework.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.