#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;}

}

#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 works in a more localized manner than Ford Fulkerson method. It works on one vertex at a time, looking only at the vertex's neighbour in the residual network. Thus it avoids examining the entire residual network to find an augmenting path. Also, they do not maintain flow conservation. Instead they maintain a preflow property which goes to say that the total flow into a vertex may exceed the flow out.

 Each vertex has an outflow pipe leading to an arbitrarily large reservoir that can accumulate fluid. In addition, each vertex, it's reservoir, and all its pipe connections sit on a platform whose height increases as the algorithm progresses. The height is used to push fluids only downhill which means from a higher vertex to a lower vertex even though there may be flows from a lower vertex to a higher vertex that may be positive.

The only outgoing flow from a vertex u that is not already saturated with flow are those that connect to vertices at the same level or at a higher level. In order to make a flow outbound from u we relabel it by pushing it one unit higher than its neighbors. This helps us rid an overflowing vertex u of its excess flow. By repeating this iteratively we get maximum flow.

The proof to show that preflow under such conditions becomes maximum will be discussed shortly.

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

#codingexercise

Void getkthfirst(node head, int k, ref int count, ref node kthfirst)

{

If (head == null) return;

count = count + 1;

if (count==k) { kthfirst = head; return;}

Getkthfirst(head.next, k, ref count, ref kthfirst);

}

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

If we define G as graph (V, E) with source s and sink t with a preflow f and a height function h, then if h(u) >= h(v) + 1, then (u,v) is not an edge in the residual network

#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 works in a more localized manner than Ford Fulkerson method. It works on one vertex at a time, looking only at the vertex's neighbour in the residual network. Thus it avoids examining the entire residual network to find an augmenting path. Also, they do not maintain flow conservation. Instead they maintain a preflow property which goes to say that the total flow into a vertex may exceed the flow out.

#codingexercise

Void getkthfirst(node head, int k, ref int count, ref node kthfirst)

{

If (head == null) return;

count = count + 1;

if (count==k) { kthfirst = head; return;}

Getkthfirst(head.next, k, ref count, ref kthfirst);

}

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

Maximum flows can also be calculated using "push-relabel" method. This method works in a more localized manner than Ford Fulkerson method. It works on one vertex at a time, looking only at the vertex's neighbour in the residual network. Thus it avoids examining the entire residual network to find an augmenting path. Also, they do not maintain flow conservation. Instead they maintain a preflow property which goes to say that the total flow into a vertex may exceed the flow out.

The excess at a vertex is the amount by which the flow in exceeds the flow out and the vertex is said to be overflowing. This method applies two operations : pushing preflow and relabeling a vertex.

Both Ford Fulkerson and Push Relabel envision the graph to be a flow network as a system of interconnected pipes of given capacities. The former uses augmenting paths in the network to give rise to an additional stream of fluid with no branches between source and sink and iteratively adds streams until there are no more. The latter assumes that each vertex has an outflow pipe leading to an arbitrarily large reservoir that can accumulate fluid. In addition, it assumes that each vertex, it's reservoir, and all its pipe connections sit on a platform whose height increases as the algorithm progresses. The height is used to push fluids only downhill which means from a higher vertex to a lower vertex even though there may be flows from a lower vertex to a higher vertex that may be positive.

The only outgoing flow from a vertex u that is not already saturated with flow are those that connect to vertices at the same level or at a higher level. In order to make a flow outbound from u we relabel it by pushing it one unit higher than its neighbors. This helps us rid an overflowing vertex u of its excess flow.

By repeating this iteratively, we induce as much flow downwards as possible. The excess in the reservoirs of the overflowing vertices is sent back up to a height higher than the source. Throughout the iterations and at this point, the preflow property holds and coverges to having no excess flow at the vertices which also results in maximum flow as the capacity constraints hold.

#codingexercise

Void getkthlast(node head, int k, ref int count, ref node kthlast)

{

If (head == null) return;

Getkthlast(head.next, k, ref count, ref kthlast);

count = count + 1;

if (count==k) { kthlast = head; return;}

}

You have a you tube video. A person watches the video in random order. You are given the start and end time of various intervals he watched. How will you confirm whether he has watched the full video or not.

Bool hasWatchedFull( interval full, List<interval> slices)
{
Var merged = merge(slices);
If (merged.first.start <= full.start && merged.last.end >= full.end && merged.sum() == full.end - full.start) return true;

return false;

}
LIst<Interval> merge(List<Interval> slices)
{
Var s = new Stack<Interval> ();
Slices.sort(); // by starting time
If (slices.count == 0) return new List<Interval>{Interval(0,0)};
If (slices.count == 1) return new List<Interval>{slices[0]};
S.push(slices[0]);
For(int i =1; i < slices.count; i++)
{
  var top = slices.top();
  If (top.end()< slices[i].start)
      S.push(slices[i]);
  Else{
     Top.end = slices[i].end;
      S.push(top);
}
Return s.toList():
}



}