[Solved] CS1501 Project1-search algorithms and symbol tables

To gain a better understanding of search algorithms and symbol tables byimplementing an autocompletion engine.

## Background:In order to make typing on a mobile device quick and easy, an autocompletefeature is commonly implemented to try to guess what word a user wishes to typebefore they are finished. Such a feature requires extensive use of searchalgorithms.

## Specifications:* First, download a copy of the English dictionary that you will use for thisproject from [here](http://people.cs.pitt.edu/~nlf4/cs1501/handouts/dictionary.txt)and place it in your repository folder* **Do not** add this file to your git repository, however! (i.e., **do not** run`git add dictionary.txt`).* You must implement a De La Briandais (DLB) trie data structure (as describedin lecture) to use in your project. The DLB trie must be all your own code(e.g., you cannot use the Java LinkedList, you must implement your own linked-list).* When your program is run, it should first create a new DLB trie and add allof the words in `dictionary.txt` to that trie (this will be the dictionarytrie).* You can assume that the file `dictionary.txt` will exist in the currentdirectory, and hardcode that _relative_ path into your program (do notuse a full path as the TA will be grading your program on a differentmachine!).* Once the dictionary trie is established, you should prompt the userto start typing a word. For this project, you will be writing only a simpleprogram to test autocomplete functionality. Due to complexities withgathering single character input in Java, you should accept a singlecharacter at a time, each followed by `Enter`. After each character,present the user with the list of predictions of the word that they aretrying to type. If the user types a number (1-5), you should consider theuser to have selected the corresponding prediction, and restart the processfor a new word. Consider `$` to be a terminator character; if the userenters a `$`, consider the characters input so far to be the full word asintended (regardless of suggestions). Finally, if the user enters a `!` atany point, your program should exit.* To generate the list of predictions, your program should not only consultthe dictionary trie, but also keep track of what words the user has enteredin the past. If the user has previously entered the same sequence ofcharacters as a prefix to a word, you should prioritize the words that mostfrequently resulted from this sequence previously. If the user has neverentered the current sequence before, or has entered fewer than 5 words withthe current seequence as a prefix (i.e., not enough words to complete thelist of 5 predictions), your program should suggest words fromdictionary.txt that have the current sequence as a prefix.* You program should propose at most 5 suggestions at a time. If there arefewer than 5 suggestions available from the users history and the dictionarytrie, then only print out the available suggestions.* If the current sequence of characters has not been entered by the userbefore and does not appear in `dictionary.txt`, you should display a messageto the user stating that no predicions were found, and allow the user tocontinue entering characters one at a time. Once the user enters a $, youshould consider the word to be finished and add it to the users history sothat you can predict it in the future.* Your program should run in a case sensitive manner in order to allow foreasier prediction of proper nouns and acronyms.* The design of the data structure that keeps track of a users previouslyentered words is entirely up to you. You must create a file named`approach.txt` that both describes your approach to implementing this symboltable and justifies your decision to take this approach. Note that this filedoes not need to be extensive, just a few lines so the TA is aware of what tolook for in your code and why you chose this approach.* The history of the users entered words should persist across runs of yourprogram. To enable this, your program should save a representation of thisdata structure to the file `user_history.txt` before exiting.* Do not add this file to your git repository! (i.e., do not run `gitadd user_history.txt`) It should be generated by your program if it doesnot exist.* Each time the user enters a character, you should use Javas[`System.nanoTime()`](https://docs.oracle.com/javase/8/docs/api/java/lang/System.html#nanoTime)to calculate how long your program takes to find the predictions. You shoulddisplay this time (in seconds) along with the list of predictions.* After the user enters `!`, your program should output the average timethat was required to produce a list of predictions.

An example run of the program would proceed as follows:

`Enter your first character: t

(0.000251 s)Predictions:(1) t (2) ta (3) tab (4) tabs (5) tabbed

Enter the next character: h

(0.000159 s)Predictions:(1) thalami (2) thalamus (3) thalamuss (4) thalidomide (5) thalidomides

Enter the next character: e

(0.000052 s)Predictions:(1) the (2) theater (3) theaters (4) theatergoer (5) theatergoers

Enter the next character: r

(0.000225 s)Predictions:(1) therapeutic (2) therapeutically (3) therapeutics (4) therapeuticss (5) therapies

Enter the next character: e

(0.000182 s)Predictions:(1) there (2) theres (3) thereabout (4) thereabouts (5) thereafter

Enter the next character: 3

WORD COMPLETED: thereabout

Enter first character of the next word: t

(0.000128 s)Predictions:(1) thereabout (2) t (3) ta (4) tab (5) tabs

Enter the next character: h

(0.000094 s)Predictions:(1) thereabout (2) thalami (3) thalamus (4) thalamuss (5) thalidomide

Enter the next character: e

(0.000085 s)Predictions:(1) thereabout (2) the (3) theater (4) theaters (5) theatergoer

Enter the next character: r

(0.000145 s)Predictions:(1) thereabout (2) therapeutic (3) therapeutically (4) therapeutics (5) therapeuticss

Enter the next character: e

(0.000130 s)Predictions:(1) thereabout (2) there (3) theres (4) thereabouts (5) thereafter

Enter the next character: !

Average time: 0.000145 sBye!`

## Submission Guidelines:* **DO NOT** add `dictionary.txt` to your git repository.* **DO NOT** add `user_history.txt` to your git repository, it must begenerated by your program.* **DO NOT SUBMIT** any IDE package files.* You must name your main program file `ac_test.java`.* You must be able to compile your program by running`javac ac_test.java`.* You must be able to run your program by running `java ac_test`.* You must fill out `info_sheet.txt`.* Be sure to remember to push the latest copy of your code back to your GitHubrepository before the the assignment is due. At the deadline, therepositories will automatically be copied for grading. Whatever is presentin your GitHub repository at that time will be considered your submission forthis assignment.

## Additional Notes:* You are free to use any data structures written by you, the textbook authors,or in the Java standard library to implement the user history symbol table.However, if you use code that you do not write yourself, you must researchthe runtime of that particular implementation and discuss that in your`approach.txt`.* Note that if your user history predictions contain a word that is alsocontained in the dictionary predictions, this word should not be presentedas a suggestion to the user twice in the same prompt (e.g., the final listof predictions in the example above).* You do not need to implement any sort of autocorrect. You can assumethat each character entered by the user is intentional.* You can assume that the user will not try to enter any numerical charactersaside from selecting a prediction.

## Grading Rubric:| Feature | Points| – | 😐 DLB trie implemented as described in class | 20| Dictionary predictions are correctly populated | 25| User history predictions are correctly populated | 30| Sufficient justification of user history approach | 10| User interaction works as specified | 5| Timing data presented | 5| Assignment info sheet/submission | 5