Learning Outcomes

This assignment achieves the Learning Outcomes of:

.  1) Analyse general problem solving strategies and algorithmic paradigms, and apply them to solving new problems;

.  2) Prove correctness of programs, analyse their space and time complexities;

.  3) Compare and contrast various abstract data types and use them appropriately;

. 4) Develop and implement algorithms to solve computational problems.

In addition, you will develop the following employability skills:

. Text comprehension.

.  Designing test cases.

. Ability to follow specifications precisely.

Assignment timeline

In order to be successful in this assessment, the following steps are provided as a suggestion. This is an approach which will be useful to you both in future units, and in industry.

Planning

1.  Read the assignment specification as soon as possible and write out a list of questions you have about it.

2. Try to resolve these questions by viewing the FAQ on Ed, or by thinking through the problems overtime.

3. As soon as possible, start thinking about the problems in the assignment.

. It is strongly recommended that you do not write code until you have a solid feeling for how the problem works and how you will solve it.

4. Writing down small examples and solving them by hand is an excellent tool for coming to a better understanding of the problem.

.  As you are doing this, you will also get a feel for the kinds of edge cases your code will have to deal with.

5. Write down a high-level description of the algorithm you will use.

6.  Determine the complexity of your algorithm idea, ensuring it meets the requirements.

Implementing

1.  Think of test cases that you can use to check if your algorithm works.

.  Use the edge cases you found during the previous phase to inspire your test cases. .  It is also a good idea to generate large random test cases.

.  Sharing test cases is allowed, as it is not helping solve the assignment.

2.  Code up your algorithm  (remember decomposition and comments), and test it on the tests you have thought of.

3. Try to break your code.  Think of what kinds of inputs you could be presented with which your code might not be able to handle.

. Large inputs

.  Small inputs

. Inputs with strange properties

. What if everything is the same?

. What if everything is different?

. etc...

Before submission

. Make sure that the input/output format of your code matches the specification.

.  Make sure your filenames match the specification.

.  Make sure your functions are named correctly and take the correct inputs.

.  Remove print statements and test code from the file you are going to submit.

Documentation

For this assignment (and all assignments in this unit) you are required to document and com- ment your code appropriately. Whilst part of the marks of each question are for documentation, there is a baseline level of documentation you must have in order for your code to receive marks. In other words:

Insufficient documentation might result in you getting 0 for the entire question for which it is insufficient.

This documentation/commenting must consist of (but is not limited to):

. For each function, high-level description of that function.  This should be a two or three sentence explanation of what this function does.

. Your main function in the assignment should contain a generalised description of the approach your solution uses to solve the assignment task.

. For each function, specify what the input to the function is, and what output the function produces or returns (if appropriate).

. For each function, the appropriate Big-O or Big-Θ time and space complexity of that function, in terms of the input size.  Make sure you specify what the variables involved in your complexity refer to.  Remember that the complexity of a function includes the complexity of any function calls it makes.

. Within functions, comments where appropriate.  Generally speaking, you would comment complicated lines of code (which you should try to minimise) or a large block of code which performs a clear and distinct task (often blocks like this are good candidates to be their own functions!).

A suggested function documentation layout would be as follows:

There is a documentation guide available on Moodle in the Assignment section, which contains a demonstration of how to document code to the level required in the unit.

1    Customized Auto-complete (10 marks)

Alice used to love the auto-complete feature in her phone until the day she sent her thesis advisor an email saying “Thank you for being on my adversary panel”.  She soon received a reply “I hope you meant the advisory panel ;)”.  Needless to say, she was embarrassed and wrote a long email (this time disabling the auto-complete feature) explaining that the mistake was caused due to the auto-complete feature.  She decided to do something about it and now wants to modify the auto-complete feature in her phone.

She has come to you for help and asks, “Can you please help me implement a customized auto-complete feature for my phone?”

“Well, I would love to help but I am quite busy with studies and  ...”, you murmur.   Alice says, “Oh come on!  I will provide you all the data, and all you have to do is to implement an algorithm”.  You desperately try to explain your situation, “Alice!  I need to start revising all the previous lectures and applied classes for FIT2004 so that I am well prepared for the final exam, and I ... ”.

Alice does not give up so easily and interrupts you, “Firstly, you should have started revising these much earlier, not in week 10.  Secondly, implementing the algorithm will strengthen your understanding which will help you in the final exam.   Finally, I know you are such a good friend!!!   Pleaseeeeeeeee  :)”.   And  before you could say something, she starts explaining the customized auto-complete feature.

The standard auto-complete function in her phone displays up to three words that have the user’s entered word as a prefix. E.g., if you are typing “adv”, the auto-complete feature shows “adversary”, “advisory” and “adventure” .  She wants to modify the auto-complete feature such that it only shows one word (instead of three) but also shows the definition of the word so that she can make sure that she is using the right word.  She also wants to know how many words are there in the dictionary that have this prefix. E.g., if there are 43 words that have “adv”  as a prefix,the auto-complete feature must display 43.

She has downloaded a dictionary from the internet that contains English words and their definitions.   She  has also downloaded the text of all the emails she has ever sent.   She  has processed the text and has assigned each word in the dictionary a frequency which corresponds to the number of times she ever used the word in her emails.  She wants the auto-complete feature to display the word in the dictionary that has the highest frequency among the words that have her entered word as a prefix.  For example, assume that the frequencies of “adversary”, “advisory”, and “adventure” are 100, 200 and 150, respectively. If she types “adv”,the modified auto-complete system should display “advisory”  with its definition and the number 43 that corresponds to the number of words that have “adv” as a prefix .  She implemented a sorting based algorithm to do the prefix matching but it is too slow. You need to help her inefficient implementation of this feature.

1.1 Input

You are provided with a file Dictionary. txt that contains 3, 000 words, their frequencies and their definitions (see Moodle).  First few words in the dictionary along with their definitions and frequencies are shown below.

Although Dictionary. txt provided on Moodle is sorted in alphabetical order of words to make it easier for you to manually verify the correctness of your implementation (and contains only the words starting with letter a), you cannot assume that the file on which your algorithm will be tested will also be sorted and will be similarly small. Your program may be tested on a different (and possibly a much larger) Dictionary.  You can assume that each word in the dictionary consists of only lowercase English letters (e.g., they do not contain white spaces, hyphens or other symbols).

You  have  been  provided  a  helper  function  called  load_dictionary(filename)  in the  file assignment2. py. You must use this function to read the input file Dictionary. txt.

The function load_dictionary returns a list of lists where the i-th element in the list corre- sponds to i-th word in Dictionary. txt represented as a list [word,  definition,  frequency]. The following shows the output of print(Dictionary[0]) after you have loaded the dictionary as above.

1.2 Output

You must write a class called Trie as follows:

You will need to create a trie as follows.

You will also need to implement the function prefix_search.  This function must return a list containing three elements  [word,  definition,  num_matches] containing the prefix matched word with the highest frequency, its definition and the number of words that have the input prefix as the prefix of the word.  If there are multiple words with the highest frequency, you must display the alphabetically smallest word (e.g., if prefix is “be”, and “best” and “beast” both have the same frequency - and highest among all words matching the prefix - your program must display “beast” because it is alphabetically smaller than “best”).  If there is no word in the dictionary that matches the input prefix, you must return a list containing  [None,None,0].    Below is a sample execution of the program for different inputs for the file Dictionary. txt provided on Moodle.

Note  that  for  the  prefix  "anac",  there  are  two  words  in  the  dictionary  anaclastic  and anacoenosis with frequency 1462 and there is no other word in the dictionary that has anac as their prefix and has frequency higher than 1462.  The algorithm returns anaclastic because it is alphabetically smaller than anacoenosis.

The last prefix in the above sample output is an empty string in which case the most frequent word in the whole dictionary is returned.

Important: Your program will be tested on a variety of test cases using an automated script.

Therefore, it is critical that your program follows the output format as shown above.

You only need to submit assignment2. py. Do not submit Dictionary. txt or any other file.

1.3    Complexity/implementation requirement

Your program will have two components.  First, you will construct a Trie.  Then, for each of call of the function prefix_search, you will need to return the relevant results.  The worst-case time complexity to construct the Trie must be O(T) where T is the total number of characters in Dictionary. txt.  The worst-case space complexity of your algorithm must also be  O(T). The complexity requirements for the function prefix_search is O(M + N) where M is the length of the prefix entered by the user and N is the total number of characters in the word with the highest frequency and its definition. Note that this is optimal because the size of the output string is O(M + N) and&nb