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.
How the path is chosen is not mentioned by the method. However the method greatly depends on this choice. If the path is chosen poorly, the method might not even terminate. It may increase the augmentations but the method need not even converge to a maximum value.  On the other hand, if the path is chosen by using a breadth first search, the algorithm runs in polynomial time.
A breadth first search proceeds like this:
BFS(G,s)
for each vertex u belonging to V - s
       u.color = white
       u.parent = nil
       u.d = infinity
s.color = gray
s.parent = nil
s.d = 0
Initialize a Queue Q
Enqueue(Q,s)
while Q is not empty
        u = Dequeue(Q)
        for each v belonging to Adj(u)
              if v.color == white
                  v.parent = u
                  v.d = u.d + 1
                  v.color = gray
                  Enqueue(Q,v)
        u.color = black
With this traversal, the maximum number of times the Ford Fulkerson method may be run to achieve a max flow f is f times because the flow increase by at least one unit in each iterartion. The time to find a path with BFS is O(V+E) = O(E) Each iteration of the while loop takes O(E) times and the total running time as O(E) * f

#puzzle
A man is allocated a task. He doubles the task done everyday. If the man completely does the task in 18 days, how many days did it take for the man to complete 25% of the task?
This is another example of where a solution is arrived at faster by working backwards from the end. In this case the full task was done in 18 days, therefore half task was done in 17 days and a quarter task was done in 16 days.  If we were to form an algebraic equation as
(x + 2x + 4x + .... 2 ^ 17 x) = 18 and then determine x to compute the first sixteen terms it would take longer.

There is an 8 by 8 chessboard in which two diagonally opposite corners have been cut off.You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board?
If we remove two squares of opposite colors each we are left with 64 -2 = 62 blocks which can be covered with thirty one dominoes equally. However by cutting the opposite corners, we are eliminating two squares of same colors which leaves us with unequal number of blacks and whites and therefore a solution is not possible.

#codinginterview
Given a set of n points in a cartesian coordinate plane, find the k closest to the origin

List<Point> GetClosestToOrigin(List<Point> points)
{
points.Sort(delegate(Point a, Point b)
{
  if (a == null && b == null) return 0;
  else if (a == null) return -1;
  else if (b == null) return -1;
  else return a.CompareTo(b);
});
return points.GetRange(0,k);
}

public class Point : IComparable {
:
public int CompareTo(object obj)
{
          // A null value means that this object is greater.
        if (obj == null)
            return 1;
        Point that = obj as Point;
        if (that == null)
            throw new ArgumentException("Object is not a Point");
        int thisdistance = this.x * this.x + this.y * this.y;
        int thatdistance = that.x * that.x + that.y * that.y;
       if (thisdistance < thatdistance) return -1;
       if (thisdistance > thatdistance) return 1;
       return 0;
}
:
}