Implement the TIRE Data Structure and use it to implement a complex algorithm
Supports Leaning Outcome 3
3. Implement data structures and algorithms in computer code.
You should have gone through all the tree based structures prior to this assignment. We are now going to move into more independent research and implementation. One of the objectives is that all students can research, implement, and use a data structure.
First take a look at the Wikipedia article on TRIE - https://en.wikipedia.org/wiki/Trie .It is worth noting that in a TRIE each node can have more than one child node, so a TRIE is NOT a binary tree.
Now let's look into what we want to be able to do with a TRIE - in this case implement a spellchecker. A spellchecker needs to determine if a word is spelled correctly, so the TRIE needs to be able to store the list of all words to check against. We must be able to add words to the TRIE, so we must implement the function;
function AddToTRIE(word)
The TRIE in the Wikipedia article uses clusters of letters, but we can also model each letter as a branch in the TRIE. The example at Top Coder takes this approach https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/ and it may be a simpler approach for you as it more closely approximates structures that you have used (like a list). This should be enough to get you started. You will still need to make some decisions of how to implement the list of nodes that are in each node. Use the bulletin board to discuss this choice.
The other algorithm that you need to implement will be to check spelling.
function CheckSpelling(word) {
returns true or false
}
Implement a TRIE that has both the functions AddToTRIE and CheckSpelling.
Once you have created the TRIE add the words (hard code) I, in, into, inlet, inn, inner, innate, ink. These are good words to use to test your TRIE
Create an interface that has one text box for entry and 2 buttons - Add To Dictionary and Spell Check. They should ad the word to the TRIE (feedback - word added) and check the word against the TRIE and return in the word was in or not in the dictionary.
Upload your Fiddle.