Consider an editor that compares a typed in word say of length n and changes it to the nearest word in the dictionary, which can be of size m. For example, if you mistyped ”floyre”, it can change the word to ”flower” or ”flow” or ”floe” or ”floor”. To judge the best word, the spell checker computes the minimum number of changes between the typed word and the words in its dictionary. The changes can be as follows; (i) inserting a character, (ii) deleting a character or (iii) changing a character. All the change operations have equal weightage.

(a) Describe an algorithm to find the minimum number of changes between two given words. This is a well-known problem in dynamic programming, so you can take help of other resources. Just explain the process in your own words (20)

(b) Using this method show step by step how to determine to which word” sdimnas” should be changed. The candidates are (i)dynast, (ii) summer, (iii)dismal, (iv)dimmer, (v)sadden. (3 × 5 = 15) (please show the stapes too)

(c) Suggest two other criteria to select the most appropriate word, excluding the minimum number of changes. Gives reasons for why you selected the criteria (5)