#algorithm discussion continued
Today we continue reading the flow networks. We were looking at max flow min cut theorem and the properties associated with it. We saw how it applied to Ford Fulkerson method. Each iteration of the method augmented the flow by considering a path in the residual network until there is no more. For each path considered, the residual capacity of that path is found and augmented to the flow network.
Maximum flow problems have a direct application in some combinatorial problems and we saw how it applied to matching in bipartite graphs. A maximum bipartite matching is a matching of maximum cardinality.
To find this maximum matching, we convert the bipartite graph into a flow network in which the flows correspond to matchings. A source s and a sink v are added to either sides of the bipartite graph. We assign directed edges from L to R with unit capacity for all edges with flows and zero otherwise. This is called an integer valued flow.
If the capacity function c takes on only integral values, then the maximum flow f produced by the Ford Fulkerson method has the property that f is an integer. Moreover for all vertices u and v, the flow f(u,v) is an integer.
We can prove this by induction on the number of iterations. Let us take only one iteration. Since the Ford Fulkerson method uses residual capacity and the capacity function is integral, we know that for the first iteration, this is trivially true.
Now let us assume that the nth iteration is an integral flow network. In the next iteration, we find the residual capacity and this will be for a path not encountered earlier. In this path, the residual capacity will be found as integer because the capacity function is integral. Any addition or subtraction from integers will result in integers. Therefore, the n+1th iteration will also result in an integer flow network. Consequently the claim holds.
Another claim made is that the cardinality of maximum matching M in a bipartite graph G equals the value of maximum flow f in a corresponding flow network G'.
This follows from the contradiction that if the corresponding flow f in G' is not maximum, then there is a maximum f' corresponding to the bipartite graph that is more than f and is integral. This corresponds to a maximum matching M' greater than M which contradicts our assumption and therefore the claim holds.
Maximum flows can also be calculated using "push-relabel" method. This method works in a more localized manner than Ford Fulkerson method.
#codingexercise
Check if a given string C is an interleaving of other two strings A  and B with non repeating characters:

Bool isInterleaved(char* A, char* B, char* C)
{
While(*C)
{
If (*C == *B)
       B++;
Else if (*C == *A)
      A++;
Else
        Return false;
}
C++;
}
Return true;
}

Permutations of  a string:
Void Permute (String a, StringBuilder b, bool[] used)
{
  If ( b.Length == a.Length)  { print b.ToString(); return;}
  For (int I = 0; I < a.Length ; i++)
  {
    If (used[i]) continue;
     used[i] = true;
     B += A[i];
     Permute(a, b, used);
     B [B.Length – 1] = ‘/0’;
     used[i] = false;
  }
}