This question is slightly different than other versions of it so please read carefully. The files were too long to post. Below are links to the files to be used. Thank you in advance!

animals.txt -> https://faculty.utrgv.edu/robert.schweller/CS3333/hwAC1/animals.txt

words.txt -> https://faculty.utrgv.edu/robert.schweller/CS3333/hwAC1/words.txt

main.cpp -> https://faculty.utrgv.edu/robert.schweller/CS3333/hwAC1/main.cpp

autocompleter.h -> https://faculty.utrgv.edu/robert.schweller/CS3333/hwAC1/autocompleter.h

CSCI 3333 Homework AC1: Autocomplete 1 Introduction A common feature of smartphone typing is autocomplete: after typing the beginning of a word, the user is presented with a list of possible completed words they intended to type. For instance, after typing "an", the user is presented with "and", "ant", "anagram", "anterior", etc. Your assignment is to implement autocomplete. Specifically, you will implement Autocompleter, a class that maintains a dictionary of words and computes the top-3 most likely completions of any input word quickly. Can chat whenever > 1 OK, let's chat this att att afternoon G after qwertyuiop Figure 1: Autocomplete suggests "afternoon" and "after" as completions of "aft". The dictionary is given as a file containing a sorted list of dictionary words and their frequencies, where higher frequency means that the word is more common (e.g. "quit" has frequency 1032 and "quixotic" has frequency 15, indicating that "quit" is a more common word). The dictionary of words and their frequencies should be stored in a balanced binary scarch tree (see Figure 2). Node. root A crocodile" -atring Entry e 515583 int freq "alpaca" 8523 "goat 52317 "albatross 5531 "cat" 468398 crow" 45921 "goose" 37393 "aardvark" 6293 armadillo" 3937 "cancel" 110050 "giraffe" 9785 "goatfish" 199 "gorilla" 19319 Figure 2: A balanced BST containing the words and their frequencies in the provided file animals.txt. Notice that the set of words that start with a given string are always consecutive in sorted order. Said another way, they're all the words in a specific range (sce Figure 3). 2 Instructions The following files have been given to you: 1. A C++ header file (autocompleter.h) declaring the Autocompleter class. 2. A C++ source file (main.cpp) containing a main function with tests. 3. A text file (animals.txt) containing 13 animals names and their frequencies in sorted order. Source: http:/orvig.comgrams/count_lu.txt. 1 Node+ root - Crocodile 16583- strings 1 -int freq Entry e "alpaca" 8523 "goat" 52317 'albatross 5531 "cat. 468398 "crow" 45921 "goose" 37393 "aardvark" 6293 "armadillo" 3937 canel" 110050 "giraffe 9785 "goatfish" "gorilla" 199 19319 Figure 3: The words starting with "a" (blue). "cr" (yellow), and "go" (green). 4. A text file (words.txt) containing 293147 common English words and their frequencies in sorted order.2 Download the files at: animals.txt words.txt main.cpp autocompleter.h Create a new C++ source file named autocompleter.cpp that implements the class declared in autocompleter.h, so that autocompleter.cpp and the provided files compile into a program that runs with no failed tests. Submit the source file autocompleter.cpp. 3 Submission and Grading Submit the aforementioned source file(s) via Blackboard as attached file(s). In the case of multiple submis- sions, the last submission before the deadline is graded. For grading, each submission is compiled with the provided files and run. Submissions that do not run to completion (i.e. fail to print "Assignment complete.") receive no credit. Submissions that take an unreasonable amount of time (e.g. more than a minute or so) to run and do not meet the asymptotic efficiency requirements receive no credit. All other submissions receive full credit. See the course late work policy for information about receiving partial credit for late submissions. Source: http:/orvig.comgrams/count_lu.txt. 2 CSCI 3333 Homework AC1: Autocomplete 1 Introduction A common feature of smartphone typing is autocomplete: after typing the beginning of a word, the user is presented with a list of possible completed words they intended to type. For instance, after typing "an", the user is presented with "and", "ant", "anagram", "anterior", etc. Your assignment is to implement autocomplete. Specifically, you will implement Autocompleter, a class that maintains a dictionary of words and computes the top-3 most likely completions of any input word quickly. Can chat whenever > 1 OK, let's chat this att att afternoon G after qwertyuiop Figure 1: Autocomplete suggests "afternoon" and "after" as completions of "aft". The dictionary is given as a file containing a sorted list of dictionary words and their frequencies, where higher frequency means that the word is more common (e.g. "quit" has frequency 1032 and "quixotic" has frequency 15, indicating that "quit" is a more common word). The dictionary of words and their frequencies should be stored in a balanced binary scarch tree (see Figure 2). Node. root A crocodile" -atring Entry e 515583 int freq "alpaca" 8523 "goat 52317 "albatross 5531 "cat" 468398 crow" 45921 "goose" 37393 "aardvark" 6293 armadillo" 3937 "cancel" 110050 "giraffe" 9785 "goatfish" 199 "gorilla" 19319 Figure 2: A balanced BST containing the words and their frequencies in the provided file animals.txt. Notice that the set of words that start with a given string are always consecutive in sorted order. Said another way, they're all the words in a specific range (sce Figure 3). 2 Instructions The following files have been given to you: 1. A C++ header file (autocompleter.h) declaring the Autocompleter class. 2. A C++ source file (main.cpp) containing a main function with tests. 3. A text file (animals.txt) containing 13 animals names and their frequencies in sorted order. Source: http:/orvig.comgrams/count_lu.txt. 1 Node+ root - Crocodile 16583- strings 1 -int freq Entry e "alpaca" 8523 "goat" 52317 'albatross 5531 "cat. 468398 "crow" 45921 "goose" 37393 "aardvark" 6293 "armadillo" 3937 canel" 110050 "giraffe 9785 "goatfish" "gorilla" 199 19319 Figure 3: The words starting with "a" (blue). "cr" (yellow), and "go" (green). 4. A text file (words.txt) containing 293147 common English words and their frequencies in sorted order.2 Download the files at: animals.txt words.txt main.cpp autocompleter.h Create a new C++ source file named autocompleter.cpp that implements the class declared in autocompleter.h, so that autocompleter.cpp and the provided files compile into a program that runs with no failed tests. Submit the source file autocompleter.cpp. 3 Submission and Grading Submit the aforementioned source file(s) via Blackboard as attached file(s). In the case of multiple submis- sions, the last submission before the deadline is graded. For grading, each submission is compiled with the provided files and run. Submissions that do not run to completion (i.e. fail to print "Assignment complete.") receive no credit. Submissions that take an unreasonable amount of time (e.g. more than a minute or so) to run and do not meet the asymptotic efficiency requirements receive no credit. All other submissions receive full credit. See the course late work policy for information about receiving partial credit for late submissions. Source: http:/orvig.comgrams/count_lu.txt. 2