Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.

Implementation of Minimum Edit Distance using Dynamic Programing. More...
#include <cassert>
#include <iostream>
#include <vector>
Namespaces  
namespace  dynamic_programming 
Dynamic Programming algorithms.  
namespace  Minimum 
Implementation of Minimum Edit Distance algorithm.  
Functions  
uint64_t  dynamic_programming::minimum_edit_distance::min (uint64_t x, uint64_t y, uint64_t z) 
Takes input of the cost of three operations: Insert, Replace and Delete and return the minimum cost among them.  
uint64_t  dynamic_programming::minimum_edit_distance::editDistDP (std::string str1, std::string str2, uint64_t m, uint64_t n) 
Calculates and stores the result of all the subproblems, so that we don't have to recur to compute the minimum cost of a particular operation if it is already computed and stored in the dp vector.  
static void  test () 
Selftest implementations.  
int  main (int argc, char *argv[]) 
main function  
Implementation of Minimum Edit Distance using Dynamic Programing.
Given two strings str1 & str2 and we have to calculate the minimum number of operations (Insert, Remove, Replace) required to convert str1 to str2.
We will solve this problem using Naive recursion. But as we are approaching with a DP solution. So, we will take a DP array to store the solution of all subproblems so that we don't have to perform recursion again and again. Now to solve the problem, We can traverse all characters from either right side of the strings or left side. Suppose we will do it from the right side. So, there are two possibilities for every pair of characters being traversed.
uint64_t dynamic_programming::minimum_edit_distance::editDistDP  (  std::string  str1, 
std::string  str2,  
uint64_t  m,  
uint64_t  n ) 
Calculates and stores the result of all the subproblems, so that we don't have to recur to compute the minimum cost of a particular operation if it is already computed and stored in the dp
vector.
dp  vector to store the computed minimum costs 
str1  to pass the 1st string 
str2  to pass the 2nd string 
m  the length of str1 
n  the length of str2 
Create a table to store results of subproblems
creasting 2D vector dp to store the results of subproblems
Fill d[][] in bottom up manner
If first string is empty, only option is to insert all characters of second string
Minimum operations = j
If second string is empty, only option is to remove all characters of second string
Minimum operations = i
If last characters are same, ignore last char and recur for remaining string
If the last character is different, consider all possibilities and find the minimum
returning the minimum cost of operations needed to convert str1 to str2
int main  (  int  argc, 
char *  argv[] ) 
main function
argc  commandline argument count (ignored) 
argv  commandline array of arguments (ignored) 
uint64_t dynamic_programming::minimum_edit_distance::min  (  uint64_t  x, 
uint64_t  y,  
uint64_t  z ) 
Takes input of the cost of three operations: Insert, Replace and Delete and return the minimum cost among them.
x  used to pass minimum cost of Insert operations 
y  used to pass minimum cost of Replace operations 
z  used to pass minimum cost of Delete operations 
x
is the minimum value y
is the minimum value z
is the minimum value returns x, if x is the minimum value
returns y, if y is the minimum value
returns z if z is the minimum value

static 
Selftest implementations.