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

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

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.

If we assumed the reverse and said that there is a path source s, v0, v1, ... ,vk, sink t where k is less than the total number of vertices n, then we know h(vi) <= h(vi+1) +1 and combining them successively we get h(s) <= h(t) + k. We already know that h(t) = 0 and k < n, so h(s) <= k < n which contradicts the invariant that h(s) = n

With the above lemmas we prove the generic push relabel algorithm as follows :
The intialization step creates a preflow.
The progress of the algorithm maintains the preflow.
At termination, there are no overflowing vertices and this preflow is a valid flow and there is no path in the residual network. Consequently, the flow is maximum.

#codingexercise

Void getcount(node head,  ref int count)

{

If (head == null) return;

getcount(head.next, ref count);

Count += 1;

}

Bool islessthanEqualTo(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 islessthanEqualto(tree1.left, tree2.left) && islessthanEqualTo(tree1.right, tree2.right);
}

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!

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

#codingexercise

Void getcount(node head,  ref int count)

{

If (head == null) return;

getcount(head.next, ref count);

Count += 1;

}

Bool islessthanEqualTo(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 islessthanEqualto(tree1.left, tree2.left) && islessthanEqualTo(tree1.right, tree2.right);
}

#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. If h(u) is greater than h(v) + 1, then (u,v) is not an edge in the residual network. This is why the original edge (u,v) is also a residual edge because we set h(u) = h(v) + 1 and we try to increase the flow in this direction.
There are two interesting observations on the push operation. First, the push operation does not depend on the heights of u and v. Second, the only qualifying residual edges only exist one level down and therefore no other heights need to be considered.
A push is a saturating push if edge (u,v) in the residual network becomes saturated and a non-saturating push otherwise. This leads to a property that after a nonsaturating push from u to v, the vertex v is no longer overflowing.
The relabel operation applies only if u is overflowing and if u.h is <= v.h for all edges. We relabel an overflowing vertex u if for every vertex v for which there is residual capacity from u to v, flow cannot be pushed from u to v because v is not downhill from u.
def relabel(u):
    u.h = 1 + min([ v.h for v in adjacencies(u)])

The generic push-relabel algorithm uses the following subroutine to create an initial preflow in the flow network

Initialize-Preflow(G,s)
for each vertex v belonging to G.V
     v.h = 0
     v.e = 0
for each edge (u,v) belonging to G.E
    (u,v).f = 0
s.h = |G.V|
for each vertex v belonging to s.Adj
     (s, v).f = c(s, v)
      v.e = c(s,v)
      s.e = s.e - c(s,v)



Now we look into the lemmas
1) An overflowing vertex can be either pushed or relabeled.
This follows from the premise that the push operation only applies to residual edges. In turn these edges (u,v) are those where the h(u) <= h(v) + 1. If the push operation does not apply, that means the h(u) is less than the h(v). Thus a relabel operation applies to u.

2) Vertex heights never decrease
When the push operation happens, we never decrease the height of u.
Whenever a relabel operation applies, its height increases by at least 1.
In the latter case,the  height of u must be less than the height of v for relabeling. Furthermore,
the height is set to one more than the minimum of the heights of all v. So there is no decrease in the height of u.

3) The execution of the generic-push-relabel method on G maintains the attribute h as a height function.
The generic-push-relabel method is as follows:
    Initialize-Preflow(G, s)
    while there exists an applicable push or relabel operation
              select an applicable push or relabel operation and perform it.

The initialize-preflow sets the preflow of all edges with source as the originating vertex to the capacity of those edges and zero otherwise. Also, the height of the source vertex is set to the absolute number of vertices.

Since the initialization is already there, the proof is by induction. If we took a residual edge (u,v) that leaves u, then the relabel operation ensures that u.h <= v.h + 1 afterwards. if the edge was incident on u from say w then
w.h <= u.h + 1 and
w.h < u.h + 1 afterwards. Thus the relabel operation  leaves h as the height function.
In the push operation, the height changes by 1 when the edge is added so the height remains a height function. When the edge is removed, the residual network removes the corresponding constraint and h again remains a height function

#codingexercise

Void getsum(node head,  ref int sum)

{

If (head == null) return;

getsum(head.next, ref sum);

Sum += head.data;

}

Bool islesser(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 islesser(tree1.left, tree2.left) && islesser(tree1.right, tree2.right);
}

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.

#codingexercise

Void getsum(node head,  ref int sum)

{

If (head == null) return;

getsum(head.next, ref sum);

Sum += head.data;

}

Bool islesser(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 islesser(tree1.left, tree2.left) && islesser(tree1.right, tree2.right);
}

#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 proof to show that preflow under such conditions becomes maximum will be discussed shortly.
We said that in a flow network represented by graph G with (V, E) as vertices and edges, let f be a preflow in G and h is a height function on V. For any two vertices u, v in the vertices V, if h(u) > h(v) + 1, then (u,v) is not an edge in the residual network. This follows from the way we have defined the operations on the flow network and the height function.
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.  The excess flow stored at a vertex u and the height are set as attributes to the vertex as u.f and u.h respectively.
The vertex u has a positive excess and the edge (u,v) has a positive residual capacity. This lets us increase the flow from u to v without u.e to become negative or the capacity c(u,v) to be exceeded by taking the minimum of the residual capacity along (u,v) and the excess flow at u. We then increase the flow with this quantity along this original edge u,v. We also decrease the same quantity from the reverse of the edge v,u  because the residual edge is the reverse of the edge in the original network.
All the flow is downward  in the flow network so all the residual edges are at the same level, one level down or upwards. If h(u) is greater than h(v) + 1, then (u,v) is not an edge in the residual network. This is why the original edge (u,v) is also a residual edge because we set h(u) = h(v) + 1 and we try to increase the flow in this direction.

#codingexercise

Void getmiddle(node head,  ref int start, ref int offset, ref node middle)

{

If (head == null) return;
Start = start  + 1;

getmiddle(head.next, k, ref count, ref offset ref middle);

Offset = offset + 1;

if (offset== start/2) { middle = head;}

}

Bool isGreater(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 isGreater(tree1.left, tree2.left) && isGreater(tree1.right, tree2.right);
}

A sorted array has been rotated r times to the left. Find r in least possible time.

Int getRotationCount(list<int> nums, list<int> sorted)
{
Return. Nums.count - Nums.merge(nums).indexof(sorted);

#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 proof to show that preflow under such conditions becomes maximum will be discussed shortly.

#codingexercise

Void getmiddle(node head,  ref int start, ref int offset, ref node middle)

{

If (head == null) return;
Start = start  + 1;

getmiddle(head.next, k, ref count, ref offset ref middle);

Offset = offset + 1;

if (offset== start/2) { middle = head;}

}