Please help

a. Complete the following graph by drawing the 21 edges that join words at Levenshtein distance 1. lake ake ace ice pace take make mike mice space taken like pike spike spice b. What is the distance (length of shortest path) in this graph between lake and like lake and pace lake and make lake and spike c. Assign a weight to each edge in the graph above based on the likelihood of making the substitution, addition, or deletion. For substitutions, base the weights on proximity of keys on a keyboard: For example, P is 4 keys away from N; F is 5 keys away from O; and D is one key away from E. For additions or deletions use weight 3. d. What is the weighted distance (minimal weight of a path) in this graph between lake and like lake and pace lake and make lake and spike e. If lake was mistakenly typed, use Part (d) to decide which of the following 4 words was most likely the intended word. like O make O pace spikeWritten Assignment 3: The Levenshtein Distance A spell checker is a word processing program that makes suggestions when it finds a word not in the dictionary. To determine what words to suggest, it tries to find similar words. One measure of word similarity is the Levenshtein distance, which measures the number of substitutions, additions, or deletions that are required to change one word into another. For example, the words spit and spot are a distance of 1 apart; changing spit to spot requires one substitution (i for o). Likewise, spit is distance 1 from pit since the change requires one deletion (the s). The word spite is also distance 1 from spit since it requires one addition (the e). The word soot is distance 2 from spit since two substitutions would be required (i for o and p for o). This situation can be represented using the graph below whose vertices are the words and the edges connect words at distance one. spite spi spot pit soot Here is another example. There are several words at distance 1 from the misspelled word "aed": aid, and, led, med. These words are included in the following graph, together with the words mad and let that are at distance 2 from aed. Note that the three words aed, aid, and and only differ by the middle letter. So they are all at distance 1 from each other forming a 'triangle' in the graph. led let aed med mad aid and