Assignment: Graph Theory
A spell checker in a word processing program 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. a) Create a graph using words as vertices, and edges connecting words with a Levenshtein distance of 1. Use the misspelled word "moke" as the center, and try to find at least 10 connected dictionary words. b) How might a spell checker use this graph? Here's some ideas on how to upload a graph:- Draw it on paper, scan it into the computer, and upload it. If your file is too large to upload, you are welcome to email it to me instead.
- Draw it on paper, take a picture with your digital camera or cell phone camera and upload it. Please make sure it's legible in the picture!
- Draw it in Paint or another computer drawing program and save it as a picture and upload it.
- In Word, use the drawing tools to create a graph, perhaps using Text Boxes and Lines. Save and upload
Download the assignment from one of the links below (.docx or .rtf):
