Spell-checking using binary search tree For each occurence of each word in a given text, it needs to be checked whether the word was spelled correctly. If not, the spell-checker will suggest possible corrections. Problem: Words appear with different frequencies. It therefore is important that the look-up operations in a dictionary can be performed efficiently. Assignments: (a) For a given binary search tree T determine the expected cost of a search in T. (b) For a given dictionary, design an efficient strategy to build a binary search tree T with mimimum expected search cost. Give a detailed explanation of your strategy and theoretically justify its efficiency. (c) Implement the strategy designed in (b) in C++. Details: Input: Dictionary with n entries and corresponding frequencies, i.e., two-dimensional array A[n]. Example: Word Frequency (in %) the 30 a 20 hat 2 xylophone 0.01 cat 5 and so on..... Output: Binary search tree constructed from the input dictionary to be used by the spell checker as well as the corresponding average search time.
Need solution to a, b, c with detailed explanation/comments in the program. The code should take as less time as possible to complete the search. The total cost of running the program should be as less as possible. Reference book... Introcuction to Algorithms.... 3rd edition MIT Press Need a solution in 4 days. I will provide two test cases for which we need the average time taken to complete the check. The key of this program is the time taken which will give the maximum no of points... Please let me know if someone can help.
the C++ program should work on windows xp and unix(netbsd) platform.