#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():
}



}