#algorithm discussion continued
Today we continue reading the flow networks. We were looking at maximum flows

Maximum flows can also be calculated using "push-relabel" method.

We reviewed relabel-to-front algorithm next.

This algorithm improves the running time of the maximum flow problem by choosing the order of basic operations carefully and managing the network data structure efficiently.

The relabel to front algorithm maintains a list of the vertices in the network. It starts from the front and scans the list repeatedly selecting an overflowing vertex u and then removing the excess at that vertex. The push and relabel operations happen as usual in the push-relabel-algorithm until u has no positive excess. On relabeling a vertex, it is moved to the front and the algorithm begins its scan again.
This algorithm works on admissible edges which are edges in the residual network through which flow can be pushed. In such case, cf(u,v) > 0 and h(u) = h(v) + 1 otherwise (u,v) is inadmissible. The admissible network consists of those edges through which we can push flow. It turns out that such as network is directed acyclic graph because if there were a cycle the heights for the vertices should remain unchanged but it increases around the cycle and this is  a contradiction.

Another property can be stated this way: If a vertex u is overflowing and (u,v) is an admissible edge, the push (u,v) applies and while it does not create any new admissible edge, it may caused the edge u,v to become admissible. This follows from the fact that when this operation is applied, the only new residual edge is the reverse edge but v is lower than u by one unit so this reverse edge becomes inadmissible. If the operation is a saturating push, then the capacity for preflow between u and v becomes zero and forward edge becomes inadmissible.

#codingquestion
Count the number of possible decodings of a given sequence if leading, trailing and consecutive zeros are excluded
For example, 121 => ABA , AU, LA
if A= 1, B =2, .. Z = 26

int countDecoding(List<int> digits, int n)
{
if (n == 0 || n == 1)
   return 1;
int count = 0;
if (digits[n-1] > 0)
     count = countDecoding(digits, n-1);
if (digits[n-2] < 2 || (digits[n-2] == 2 && digits[n-1] < 7))
       count += countDecoding(digits, n-2);
return count;
}

void decode(List<int>digits, int n, ref stringbuilder s, ref List<string> results)
{
if (n == 0) {results.Add(s.reverse()); return;}
if (n == 1) { s += ToLetter(digits, n-1, 1); results.Add(s.reverse()); return; }
if (digits[n-1] > 0){
      s += ToLetter(digits, n-1, 1);
     count = countDecoding(digits, n-1);
      s.RemoveLast();
}
if (digits[n-2] < 2 || (digits[n-2] == 2 && digits[n-1] < 7)){
       s += ToLetter(digits, n-2, 2);
       count += countDecoding(digits, n-2);
       s.RemoveLast();
}
}

Yesterday we discussed stars and bars theorems. If we were to apply this to distribute say seven indistinguishable one dollar coins the distributions are essentially equivalent to tuples of three positive integers  whose sum is 7. There fore there are binomial coefficient n-1 choose k-1 ways or 6 choose 2  = 6! / (2! 4!) = 15 ways.

Reverse every k nodes of a linked list
Void reverseK(node head, int k)
{
Int n = 0;
For( node cur = head; cur; cur=cur.next) n++;
Node cur = head;
Node prev =null;
Node root = null;
For(int i = 0; i < n/k+1; i++)
{
Node next=cur;
For(int j = 0; next && j <k-1; next=next.next, j++);
Node Temp = null;
If (next){
temp = next.next;
Next.next = null;
}
Reverse(ref cur);
Node head =cur;
If(!root) root = head;
While(cur.next)cur=cur.next;
If(!prev){
Prev = cur;
}else {   prev.next=head; prev = cur;}
Cur=temp;
}
Return root;
}