SIG Algorithm Challenge 2: You’re Going to Have to Trie Harder Than That!

Solutions (any language) due at Midnight on Thursday (03/01/2018)

The Problem

A couple of weeks ago we took a look at radix trees, a type of compressed trie which can be used for storing strings. This week, your mission (should you choose to accept it) is to put the theory we learned into practice and implement your own radix tree. For the bold – and the bonus – you can also optionally use that tree to implement a predictive text program (whatever that means to you).

Missed our string manipulation meeting? No worries! Check out our meeting notes and all of the fantastic online resources to get yourself up to speed. If you have any more questions, hit up the Discord or email me at ms2286@njit.edu

 

The Requirements

The test input is in this folder, both with Windows and with Unix line endings.

  • Your program must read in input from a .txt file. The file will have one word per line, all lowercase.
  • Each of the words must be inserted into a radix tree.
  • Print out the final tree, which must contain every single input word.

A few notes:

  • You don’t need to implement remove or search methods for the radix tree, just insertion and print.
  • Any valid radix tree will be accepted; the order or arrangement of the nodes is not important, as long as all the words are present.
  • If there is no compression, it’ll count as a trie (100 points) rather than a radix tree (200 points).

 

Scoring

100 points for implementing the above program using a trie (an uncompressed radix tree) – and also for coming to our weekly meeting on Tuesdays!

100 bonus points (on top of your score) if your solution gives the most compact tree

200 points for giving a working solution that uses a radix tree.

500 points for giving a working solution with a radix tree, and then using that radix tree to implement predictive text in some way. What that means is up to you, as long as you can convince me that what you’ve made fits this description. What I have in mind (and this is a suggestion rather than a rule) is that ideally, the user should start typing a word and be presented with potential completions for that word as they are typing, without needing to hit enter after each letter.

What don’t you need to do?

  • The predictions don’t have to be instant, but they should come quickly enough to be able to “help” the user type their words.
  • The program doesn’t need to actually fill in the rest of the word for the user (but that would certainly be an impressive cherry on top.)

For the bonus testing, I’ll be doing two things: typing a word that is in the tree, and typing a word that isn’t in the tree. If you go for this, just be sure your program can handle both cases.

Send all solutions/questions/concerns to ms2286@njit.edu

Advertisements
%d bloggers like this:
search previous next tag category expand menu location phone mail time cart zoom edit close