Topics: Dynamic programming: Edit Distance (print table, find most similar words in the dictionary). Unless otherwise specified, you should always assume that every function you are asked to implement...

Topics: Dynamic programming: Edit Distance (print table, find most similar words in the dictionary).
Unless otherwise specified, you should always assume thatevery function you are asked to implement has to work for all sizes and variations of the data.

In this assignment you will:

1. Implement the Edit Distance between 2 strings as shown in class.


2. Print the distance matrix as a formatted table. (This will help you debug your implementation of the edit distance function.)


3. Spell check. Read data from 2 files (a dictionary and a test file) and then for each word in the test file you will compute the Edit Distance to the words in the dictionary, print the smallest distance and all the dictionary words that are at that distance from the current test word.

1. 
   edit_distance_client.c- do not modify


2. 
   edit_distance.h- do not modify


3. 
   edit_distance.c- write your solution code here.


4. 
   data1.txt- file to be used for input redirection


5. 
   test1.txt- test file (with misspelled words). File format:

   
   N word1 word2 ... wordN
   

   
   


6. 
   dictionary1.txt- dictionary file. This file is a slight modification of the 1-1000.txt file fromhttps://gist.github.com/deekayen/4148741.
   It has the same file format as the test file.


7. 
   runStubs.html- sample run of the given files (required methods are NOT implemented in edit_distance.c)


8. 
   runSolution.html- sample run of complete solution (required methods are implemented)


9. 
   runUserInput.html- sample run with input given by user (NOT input redirection from a file).

1. All the arrays and other data must be passed as arguments. They cannot be global variables. 50% of task credit lost if an array (1D or 2D) is a global variable instead of being passed as an argument.


2. The program must not have any memory errors when ran with Valgrind.


3. The table showing the cost must show the numbersaligned exactly as shown in the sample run: 3 spaces for number display in each cell and horizontal lines for the table.


4. You can assume that any string is at most 100 characters long. That includes: the words (given by the user or in test and dictionary files) and the file names themselves.


5. Do not modify the signature of any of the functions given in the .h file.


6. In order to implement the required two methods, you are encouraged to write other functions to do smaller parts of the work. (You will put those functions in the edit_distance.c file.)


7. Do not hardcode file names or the number of words/lines in files.

1. You can work on the table display before you implement the edit distance (you can print 0 in every cell).


2. You can work on reading the dictionary and test words from the files even before you implement the edit_distance function.


3. If you need to read-up on passing 2D arrays as arguments in C you can check this page:https://www.geeksforgeeks.org/pass-2d-array-parameter-c/.


4. Run your code with both input redirection AND user input. See therunUserInput.htmlfor a sample run.