The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

# Algorithms

## Dynamic Programming

Problem :-
Solve the Edit Distance problem.
Edit Distance between two strings is the cost involved in converting one string to another.
For conversion, we can use three kind of operations ( INSERT, DELETE & REPLACE ).
Assume the costs of insertion, deletion and replacing as 1.
So, the problem is to find out minimum number of edits required to convert one string to another.
For e.g, minimum edits required to convert sunflower to sunlight is 5

Solution :-
Suppose we need to convert a string ( str1 ) of size m to a string ( str2 ) of size n with minimum number of edits.
First we will consider a smaller subproblem and define an optimal structure of the solution.
Let Cost ( i , j ) denotes the minimum cost to convert first ' i ' characters of str1 to first ' j ' characters of str2.
There are 2 possibilities :
1 ) if str1 ( i ) == str2 ( j ) , problem is reduced to finding Cost ( i - 1 , j - 1 ) ( no edit required )
2 ) if str1 ( i ) != str2 ( j ) , then we can choose any of the following edit operations :
Insert : problem reduces to finding Cost ( i , j - 1 ) + INSERT_COST
i.e we insert the mismatched character and add the cost of insertion.
Delete : problem reduces to finding Cost ( i - 1 , j ) + DELETE_COST
Replace : problem reduces to finding Cost ( i - 1 , j - 1 ) + REPLACE_COST
Now, our objective is to find minimum edit cost i.e to minimize Cost ( i , j ) . So, we will consider the minimum of the values of above subproblems or possibilities and the optimal structure of the solution is defined as :
Cost ( i , j ) = min [ Cost ( i , j - 1 ) + I , Cost ( i - 1 , j ) + D , Cost ( i - 1 , j - 1 ) + R ] if str1 ( i ) != str2 ( j ) and
Cost ( i , j ) = Cost ( i - 1 , j - 1 ) if str1 ( i ) == str2 ( j )
Now, we can find Cost ( i , j ) for any values of i and j.
Finally, Cost ( m , n ) gives the required minimum edit cost to convert str1 to str2.