int edit_distance (string A, string B) { m = A.length(); n = B.length(); for (int i = m; i >= 0; i--) { for (int j = n; j >= 0; j--) { if (i == m) d[i][j] = 2 * (n - j);

else if (j == n) d[i][j] = 2 * (m - i);

else if (A[i] == B[j]) { d[i][j] = d[i + 1][j + 1]; }

else d[i][j] = min(2 + d[i][j + 1], min(2 + d[i + 1][j], 1 + d[i + 1][j + 1]));

} }

return d[0][0];

}

Experimental Analysis Re-implement edit_distance() without dynamic programming (using recursion only). Run the recursive solution and the dynamic programming solution on your machine to compare their running times (you will need to add code for printing out the running times). Provide the names of the test cases you have used and the time in seconds or milliseconds) for each test case. If you used test cases that you have created, then mention only the size of strings A and B. You must use at least 4 different test cases and the running time of the non-dynamic programming solution on at least three of the test cases must be greater than 1 second. Provide your answer in a table as follows: length of A length of B File Name (if available) Time (DP) Time (recursive) 1 2 3 4