#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.

This method performs two basic operations: pushing flow excess from a vertex to one of its neighbors and relabeling a vertex.

The Push operation applies only if u is an overflowing vertex, cf(u,v) > 0 and h(u) = h(v) + 1. The push operation updates the preflow f and the excess flows for u and v. It assumes that we can compute residual capacity in constant time given c and f.

All the flow is downward  in the flow network so all the residual edges are at the same level, one level down or upwards. we discussed the following lemmas

1) An overflowing vertex can be either pushed or relabeled.

2) Vertex heights never decrease

3) The execution of the generic-push-relabel method on G maintains the attribute h as a height function.

4) Another lemma that gives ank important property on the height function states that 

 If f is a preflow in the flow network G, then there is no path from source to sink through the residual network Gf.

With the above lemmas we proved the generic push relabel algorithm.

#codingexercise

Void getcounthigher(node head, int k,  ref int count)

{

If (head == null) return;

getcounthigher(head.next, k,  ref count );

If (head.data > k) Count += 1;

}

Bool ismorethanEqualTo(node tree1, node tree2)
{
if (tree1 == null && tree2 == null) return true;
if (tree1 == null || tree2 == null) return false:
if(tree1.data < tree2.data) return false;
Return ismorethanEqualto(tree1.left, tree2.left) && ismorethanEqualTo(tree1.right, tree2.right);
}

#puzzle
How many binary search trees are possible from a sequence of n numbers ?

The nunber of binary search trees is the nth Catalan number.
1/(n+1) 2n C n
= (2n)!/ (n+1)!n!
Let us say node i is chosen to be the root. Then there are i-1 nodes smaller than i and n-i nodes bigger than i If t(n) is the total number of BSTs, then t(n) = sum t(i-1).t(n-1) for i = 1 to n
t(2) = t(0)t(1) + t(1)t(0) = 2
t(3) = t(0)t(2)+t(1)t(1) + t(2)t(0) = 5

By finding the catalan numbers for lower numbers of n we can reconstruct the values for higher numbers.

Find the number of ways of arranging n items in k groups
The answer is (n+k-1)!/n!(k-1)!

The reasoning can be intuitively explained as follows. We position items and groups along a line. The number of arrangements is equivalent to what we need. If we fix the positions of items, the positions of the group fall in place. This is simply n+k-1 choose n.