1        (80 marks)     t9 predictive text technology

T9, which stands for Text on 9 keys, was a predictive text technology used in the late 1990s for mobile phones, specifically those that contain a 3 x 4 numeric keypad as shown in Figure 1.    T9’s objective was to make it easier to type text messages. It allowed words to be entered by a single key press for each letter, as opposed to the multi-tap approach used in conventional       mobile phone text entry at the time, in which several letters were associated with each key, and selecting one letter often required multiple key press. For example, to type the word the, the user had to type 3 keys 8-4-3 with predictive text technology as opposed to five key strokes 8-4-4-3-3 for "multi-tap" technology.

In ideal predictive text entry, all words used are in a given dictionary, punctuation are ignored, no spelling mistakes are made, and no typing mistakes are made. The user presses the number   corresponding to each letter and, as long as the word exists in the predictive text dictionary it will appear. For instance, pressing 4-6-6-3 will typically be interpreted as the word good, provided  that a linguistic database in English is currently in use, though alternatives such as home, hood and hoof are also valid interpretations of the sequence of key strokes.

The aim of this question is to retrieve all valid words (that is in a given dictionary) corresponding to a sequence of key strokes from a 3 x 4 numeric keypad. For simplicity, we assume all          characters are lower case.

Figure 1: Example of a 3 x 4 numeric keypad used for T9.

(i)       [15 marks]     For this question, you must use the file T9Pad.java provided. The class          T9Pad represents a numeric keypad. The mapping between alphabet characters and number is stored in the attribute pad. The attribute pad is a HashMap where keys are Integer and    values are Set<Character>.

Implement public  Integer  getKeyCode(Character  letter) which returns the digit associated with the character letter. If there are no mapping for this character, the      method must return an IllegalArgumentException.

For example, assuming we only added the mapping  (2,  "abc") via the method addKey, getKeyCode(’a’) should return 2, whereas getKeyCode(’d’) must throw an           exception.

(ii)      [15 marks]     Implement public  List<Character>  getPadLetters() in the class T9Pad which returns all the alphabet characters currently represented in the pad. The method should return an empty list if there are no mapping between numeric values and characters.

(iii)     [20 marks]     Words produced by the same combination of keypresses have been called          "textonyms". For example, the key sequence 4663 on a keypad, correspond to the words good as well as other words, such as home, gone and so on. the words good, home and gone are   "textonyms".

Implement public  boolean  isTextonym(String  word1,  String  word2) in  the class T9Pad which returns true if word1 and word2 are textonyms, false otherwise.

(iv)     [15 marks]     For the reminder of the question, complete the implementation of the class          T9Tree. This class represents the dictionary of all words known by the user. In order to have an efficient predictive text application, we have decided to represent the data structure as a tree (see Figure 2). Each node represents the set of words that can be type using the numeric         sequence from the root to that node. For example, to type the word go, we have to press the    keys 4 then 6. Starting from the root, we must go to the child 6, then child 4 of child 6. For longer words such as home we keep going down the tree branches. In addition, the root cannot have  any words, hence an empty set of words for the root.

Implement the method public  Set<String>  getAllWords() which returns all the known word in that tree.

Figure 2: Tree structure to implement T9 predictive text. Each node can have up to 10 children.

(v)      [15 marks]     Implement public  Set<String>  getAllWords(String  t9code)   which returns all the known words in that tree such as their numeric code has the prefix t9code. For example getAllWords("4663") should returns a set containing "good", "goods", "goodies", "home", "homes" to list a few. If no known word have such a prefix, the          method returns an empty set. The method throws an IllegalArgumentException if the t9code contains keys that are not part of the numeric pad.

Note, if t9code is an empty String, the method should return all words in the tree. In this case the result is the same as calling getAllWords().

2        (20 marks)     Recursion

The code for this question must be written in the provided file

ManufacturingProcess.java.

Warning: if the implemented methods in this question are not recursive, a mark of 0 will be awarded for that part of the question.

The aim of this question is to evaluate the cost of transforming a manufacturing process PA into another manufacturing process PB. Each manufacturing process is composed of many

sub-processes. For simplicity, a manufacturing process is represented as an array of Strings, where each string is the name of a sub-process. For example a process composed of three  sub-processes is represented by an array such as {"P211",  "P011",  "P256"}.

We want to quantify how different the two processes are. There are three possible operations that can be performed, insertion, deletion and substitution. For example, let’s consider the     manufacturing processes PA = {P011,  P101,  P200,  P200,  P123,  P256} and       PB = {P311,  P101,  P200,  P200,  P101,  P256,  P004}. A minimal modification  script that transforms PA into PB is:

1.  substitution of P311 for P011,

2.  substitution of P101 for P123,

3.  insertion of P004 at the end.

Assuming that each operation has a cost of 1, the modification script has a total cost of 3.

This problem has optimal substructure. That means the problem can be broken down into       smaller, simple “sub-problems”, which can be broken down into yet simpler sub-problems, and so on, until, finally, the solution becomes trivial.

Problem: Transform manufacturing process PA [1..m] into PB [1..n] by performing a series of change on PA[1..m]. Note, the indexation of processes here starts at 1.

Sub-problem: Transform a manufacturing sub-process PA [1..i] into PB [1..j] by performing a series of change on PA [1..i], where i s m and j s n.

1.  We have reached the end of either manufacturing sub-process.

•  If PA is empty (i = 0), insert all remaining processes of manufacturing sub-process PB [1..n] into PA. The cost of this operation is equal to the number of processes left in PB .

•  If PB is empty (j = 0), remove all remaining processes of manufacturing sub-process PA [1..i]. The cost of this operation is equal to the number of processes left in PA .

2.  The last processes of manufacturing sub-processes PA [1..i] and PB [1..j] are the same. Nothing needs to be done we simply recurse for the remaining sub-processes, that is    PA [1..i - 1] and PB [1..j - 1]. As no modification is involved, the cost will be 0.

3.  The last processes of PA [1..i] and PB [1..j] are different. In that case return the minimum of the following operations with an added cost of 1, the cost of the actual operation:

•  Insert the last process of PB [1..j] into PA [1..i]. The size of PB [1..j] reduces by 1, and PA [1..i] remains the same.

•  Delete the last process of PA [1..i]. The size of PA [1..i] reduces by 1, and PB [1..j] remains the same.

•  Substitute (Replace) the current process PA [i] of PA by the current process PB [j] of PB. The size of both sub-processes reduces by 1.

In this approach, we look at the last process of each manufacturing processes (using indices i and j to define the last process of a sub-problem), we could have done something similar by   looking at the first processes instead.

As you can see, we can define the problem recursively as:

i

 j

costi,j  =．．．costi -1,j -1  1 + min ．

,              ,

if j = 0 (deletions)

if i = 0 (insertions)

if PA [i] = PB [j] (do nothing)

costi -1,j         deletion

costi,j -1        .insertion

costi -1,j -1   substitution

(1)