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

We reviewed relabel-to-front algorithm next. This algorithm improves the running time of the maximum flow problem by choosing the order of basic operations carefully and managing the network data structure efficiently.  We saw what admissible edges are. If a vertex u is overflowing and (u,v) is an admissible edge, the push (u,v) applies and while it does not create any new admissible edge, it may cause the edge u,v to become admissible. The admissible edges also applies to relabel operation
We also saw how the discharge operation takes place and how the relabel-to-front algorithm proceeds.
Since the relabel-to-front algorithm iterates on vertices other than the source or sink, this is best done in the form of topological sort of the vertices in the admissible network.

The Relabel to front algorithm computes maximum flow. It is in fact a push-relabel method. It uses discharge to do push and relabel only when they apply. The algorithm maintains the following invariant.
The vertex being discharged of its excess flow from the list of vertices has no vertex earlier in the list that has excess flow.
This means that the vertices are taken in topological sort order.

#preorder without recursion
void preorder(node root)
{
var current = root;
var stk = new Stack<node>();

while(current != null || stk.empty() == false)
{
if (current != null)
{
Console.Write(current.data);
stk.push(current);
current = current.left;
continue;
}
if (stk.empty() == false)
{
current = stk.pop();
current = current.right;
}
}
}

#postorder without recursion
void postorder(node root)
{
var current = root;
var stk = new Stack<node>();
Var last = null;
Var peek = null;
while(current != null || stk.empty() == false)
{
if (current != null)
{
stk.push(current);
current = current.left;
Continue;
}else
    Peek = stk.peek();

If(peek.right != null && peek.right!=last){
    Current = peek.right;
}
Else{
Console.Write(peek.data);
Last = stk.pop();

}
}
}
}

Given an array of n elements, where each element is at most k away from its target position, sort the array

Void sortK(ref List<int> A, int k)
{
Assert(A.count > k);
Var h = new Heap<int>();
For (int i =0: i < k && i < n; i++)
{
h.Add(A[i]);
}
Int i = k+1;
For(int j =0; j < n; j++)
{
   If (i < n){
       A[j] = h.replaceMin(A[i]);
       I ++;
}else{
      A[J]  = h.min()
}
}
}

The above also works for reverse order sorting except that we need to substitute min heap for max heap

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

We reviewed relabel-to-front algorithm next. This algorithm improves the running time of the maximum flow problem by choosing the order of basic operations carefully and managing the network data structure efficiently.  We saw what admissible edges are. If a vertex u is overflowing and (u,v) is an admissible edge, the push (u,v) applies and while it does not create any new admissible edge, it may cause the edge u,v to become admissible. The admissible edges also applies to relabel operation
We also saw how the discharge operation takes place and how the relabel-to-front algorithm proceeds.
Since the relabel-to-front algorithm iterates on vertices other than the source or sink, this is best done in the form of topological sort of the vertices in the admissible network.
#codingexercise
Print all nodes that are a distance k from leaf

Void GetK(Node root, int k, ref List<int> path, ref list<int> visited, ref int count)

{

if (root== null) return;
path[count] = root.data;
visited[count] = false;
count += 1;

if (root.left == null && root.right == null &&
     Count-k-1==0 && visited[count] ==false)

{
Console.write(path[count-k-1]);
visited[count] = true;
}

root.left= GetK(root.left, K, ref path, ref visited, ref count);

root.right = GetK(root.right, K, ref path, ref visited, ref count);

}

The above method assumes each element is visited in inorder

#Inorder without recursion
void inorder(node root)
{
var current = root;
var stk = new Stack<node>();

while(current != null || stk.empty() == false)
{
if (current != null)
{
stk.push(current);
current = current.left;
continue;
}
if (stk.empty() == false)
{
current = stk.pop();
Console.Write(current.data);
current = current.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.

We reviewed relabel-to-front algorithm next. This algorithm improves the running time of the maximum flow problem by choosing the order of basic operations carefully and managing the network data structure efficiently.  We saw what admissible edges are. If a vertex u is overflowing and (u,v) is an admissible edge, the push (u,v) applies and while it does not create any new admissible edge, it may cause the edge u,v to become admissible. The admissible edges also applies to relabel operation

The discharge operation proceeds like this :

While there is a neighbor to u, apply the following operations. Set v to the current neighbor. If v is nil, apply the relabel operation to u. Reset the current to the head of the new neighbor list. If v is not nil and the capacity of preflow from u to v is greater than zero and the height of u is one level greater than that of v, apply the push operation on (u,v). If neither relabel nor push occurs, skip to the next neighbor.

The Relabel to front algorithm proceeds on a flow network G with source s and sink t this way. We initialize the preflow in the network. We choose a set of all vertices in G excluding the source and sink and in arbiyrary order. For each vertex in this set, We set its current to head. We start with the head of the set L as u. While u is not nil, we peform the following operations. We remember the old height of u. Then we appy the diacharge method to u. If the height of u is greater than the old height, we move u to the front of list L. We choose the next u.

#codingexercise

Given a binary tree, defining a term “complete path sum” as, sum of values of nodes lying in a path from root to the leaf; Now given a value ‘k’, we have to find the k-light  path and prune the binary tree i.e. prune/delete nodes for which complete path sum is greater than k.

node PruneKLight(Node root, int K, ref int sum)

{

if (root== null) return;

sum += root.data;

root.left= PruneKLight(root.left, K, ref sum);

root.right = PruneKLight(root.right, K, ref sum);

if (root.left == null && root.right == null) 

{

if (sum > k ){

Sum -= root.data;

delete root;

root = null;

Return root;

}

}

sum-=root.data;

return root;

}

Given a BST, transform it into greater sum tree where each node contains sum of all nodes greater than that node.
void ToGreater(Node root, ref int sum)
{
if (root == null) return;
// reverse inorder
ToGreater(root.right, ref int sum);
sum += root.data;
root.data = sum-root.data;
ToGreater(root.left, ref int sum);
}

Given a BST, transform it into lesser sum tree where each node contains sum of all nodes lesser than that node.
void ToLesser(Node root, ref int sum)
{
if (root == null) return;
ToLesser(root.left, ref int sum);
Var val = root.data;
Root.data = sum;
sum += val;
ToLesser(root.right, ref int sum);
}

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

We reviewed relabel-to-front algorithm next. This algorithm improves the running time of the maximum flow problem by choosing the order of basic operations carefully and managing the network data structure efficiently.  We saw what admissible edges are. If a vertex u is overflowing and (u,v) is an admissible edge, the push (u,v) applies and while it does not create any new admissible edge, it may cause the edge u,v to become admissible. The admissible edges also applies to relabel operation.

Now we see neighbor lists. Edges in this algorithm are organized into "neighbor lists". Given a flow network G = (V,E), the neighbor list is simply a linked list of vertices v for which there may be a residual edge (u,v).  The relabel to front algorithm cycles through each neighbor list in an arbitrary order that is fixed throughout the execution of the algorithm.

The neighboring vertices are the ones to which the excess flow at u is discharged through admissible edges. This discharge operation includes relabeling to cause edges leaving u to become admissible. As we know relabel operations are performed when push is not possible and this iteration happens for each vertex in the neighboring list. If the relabel happens, the neighboring list is reset and the currently evaluated neighbor points to the head. If the push happens, the current is not changed because this may be repeated. If neigher push nor relabel applies, the current is updated to the next neighbor.

In fact, one of the properties of the discharge operation is that when it calls push, the push applies to (u,v) and when it calls relabel, the relabel applies to (u,v). The relabel only applies when we can show that all the edges leaving u are inadmissible. This depends on the neighbors and their number. If the discharge starts and ends with the head of the list, all the edges are inadmissible.  The list may not be completely traversed as the current is not always updated.

When the list is completely traversed, the calls, the procedure relabels u. This resets the pass and to pass over a neighbor, the edge(u,v) must be deemed admissible. Since the initialization and progress guarantee that each neighbor is evaluated, all the edges leaving u have been deemed inadmissible. At the termination of the pass, push operations do not create admissible edges and the only other operation relabel must have but a relabeled vertex has no entering admissible edges and u is not relabeled. Therefore at the end of the pass, all edges leaving u remain inadmissible.

#codingexercise

Given a BST find the maximum N elements in the tree

List<node> GetMaxN(node root, int N)

{

var inorder = ToInOrder(root);

assert (inorder.Count > N);

return inorder.GetRange(inOrder.Count - N, N).ToList();

}

Another way to do this would be to augment the tree data structure with the rank of the node. The rank informs how the number of elements in the right subtree of the current node. It stands for the number of nodes that have value more than the current. If the rank is N-1, then the current node inclusive and the right subtree are the number of nodes required.

void GetMaxN(node root, int N, ref List<Node> nodes)

{

if (!root) return;

GetMaxN(root.left, N, ref nodes);

if (root.data > N) { GetMaxN(root.right, N, ref nodes); }

else {

nodes.Add(root);

GetMaxN(root.right, N-1, ref nodes);

}

}

The same holds for finding the minimum N elements in the tree

List<node> GetMinN(node root, int N)

{

var inorder = ToInOrder(root);

assert (inorder.Count > N);

return inorder.GetRange(0, N).ToList();

}

Given a binary tree, defining a term “complete path sum” as, sum of values of nodes lying in a path from root to the leaf; Now given a value ‘k’, we have to find the k-heavy path and prune the binary tree i.e. prune/delete nodes for which complete path sum is smaller than k.

node PruneKHeavy(Node root, int K, ref int sum)
{
if (root== null) return;
sum += root.data;
root.left= PruneKHeavy(root.left, K, ref sum);
root.right = PruneKHeavy(root.right, K, ref sum);
if (root.left == null && root.right == null) 
{
if (sum < k ){
Sum -= root.data;
delete root;
root = null;
Return root;
}
}
sum-=root.data;
return root;
}

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

We reviewed relabel-to-front algorithm next.

This algorithm improves the running time of the maximum flow problem by choosing the order of basic operations carefully and managing the network data structure efficiently.

The relabel to front algorithm maintains a list of the vertices in the network. It starts from the front and scans the list repeatedly selecting an overflowing vertex u and then removing the excess at that vertex. The push and relabel operations happen as usual in the push-relabel-algorithm until u has no positive excess. On relabeling a vertex, it is moved to the front and the algorithm begins its scan again.

This algorithm works on admissible edges which are edges in the residual network through which flow can be pushed. In such case, cf(u,v) > 0 and h(u) = h(v) + 1 otherwise (u,v) is inadmissible

Another property can be stated this way: If a vertex u is overflowing and (u,v) is an admissible edge, the push (u,v) applies and while it does not create any new admissible edge, it may cause the edge u,v to become admissible.

The admissible edges also applies to relabel operation. If a vertex u is overflowing and there are no admissible edges leaving u, then relabel of the vertex u applies. After this operation, there is at least one admissible edge leaving u but there are no admissible edges entering u. Recall that an admissible edge is one where we can push flow and its not saturated yet. Also the relabel operation applies to a vertex that is overflowing and to an edge that is upwards or at same level and by definition, there must be one edge outbound from u so that the flow occurs and the height of u increases. Relabel gives u the greatest height allowed by the constraints on heights function. Initially there was no admissible edges leaving u and consequently no push possible and that was why the relabel occurred.After the relabel the height of u is adjusted to be one unit higher than the a minimum v and hence one outbound edge. At this time there are no admissible edges entering u because if it were the destination vertex v would be higher than one level over height of u before the relabel and we know already there are no residual edges between vertices whose heights differ by 1. Also relabel does not change the residual network. Therefore the property that there are at least one admissible edge leaving u but there are no admissible edges entering u.

#codingexercise

Given two rectangles, find whether they are overlapping or not?
static bool intersects(Rectangle r1, Rectangle r2)
{
bool isdisjoint = false;
// are  they disjoint along x axis ?
if (r1.tl.x < r2.tl.x)
   isdisjoint = r1.br.x < r2.tl.x;
else
  isdisjoint = r2.br.x < r1.tl.x;
if (isdisjoint == true) return false;

// are they disjoint along y-axis ?
if (r1.br.y < r2.br.y)
   isdisjoint = r1.tl.y < r2.br.y;
else
  isdisjoint = r2.tl.y < r1.br.y;
return isdisjoint == false;
}
https://d.docs.live.net/d609fb70e39b65c8/AppInfrastructure.doc

 

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

We reviewed relabel-to-front algorithm next.

This algorithm improves the running time of the maximum flow problem by choosing the order of basic operations carefully and managing the network data structure efficiently.

The relabel to front algorithm maintains a list of the vertices in the network. It starts from the front and scans the list repeatedly selecting an overflowing vertex u and then removing the excess at that vertex. The push and relabel operations happen as usual in the push-relabel-algorithm until u has no positive excess. On relabeling a vertex, it is moved to the front and the algorithm begins its scan again.
This algorithm works on admissible edges which are edges in the residual network through which flow can be pushed. In such case, cf(u,v) > 0 and h(u) = h(v) + 1 otherwise (u,v) is inadmissible. The admissible network consists of those edges through which we can push flow. It turns out that such as network is directed acyclic graph because if there were a cycle the heights for the vertices should remain unchanged but it increases around the cycle and this is  a contradiction.

Another property can be stated this way: If a vertex u is overflowing and (u,v) is an admissible edge, the push (u,v) applies and while it does not create any new admissible edge, it may caused the edge u,v to become admissible. This follows from the fact that when this operation is applied, the only new residual edge is the reverse edge but v is lower than u by one unit so this reverse edge becomes inadmissible. If the operation is a saturating push, then the capacity for preflow between u and v becomes zero and forward edge becomes inadmissible.

#codingquestion
Count the number of possible decodings of a given sequence if leading, trailing and consecutive zeros are excluded
For example, 121 => ABA , AU, LA
if A= 1, B =2, .. Z = 26

int countDecoding(List<int> digits, int n)
{
if (n == 0 || n == 1)
   return 1;
int count = 0;
if (digits[n-1] > 0)
     count = countDecoding(digits, n-1);
if (digits[n-2] < 2 || (digits[n-2] == 2 && digits[n-1] < 7))
       count += countDecoding(digits, n-2);
return count;
}

void decode(List<int>digits, int n, ref stringbuilder s, ref List<string> results)
{
if (n == 0) {results.Add(s.reverse()); return;}
if (n == 1) { s += ToLetter(digits, n-1, 1); results.Add(s.reverse()); return; }
if (digits[n-1] > 0){
      s += ToLetter(digits, n-1, 1);
     count = countDecoding(digits, n-1);
      s.RemoveLast();
}
if (digits[n-2] < 2 || (digits[n-2] == 2 && digits[n-1] < 7)){
       s += ToLetter(digits, n-2, 2);
       count += countDecoding(digits, n-2);
       s.RemoveLast();
}
}

Yesterday we discussed stars and bars theorems. If we were to apply this to distribute say seven indistinguishable one dollar coins the distributions are essentially equivalent to tuples of three positive integers  whose sum is 7. There fore there are binomial coefficient n-1 choose k-1 ways or 6 choose 2  = 6! / (2! 4!) = 15 ways.

Reverse every k nodes of a linked list
Void reverseK(node head, int k)
{
Int n = 0;
For( node cur = head; cur; cur=cur.next) n++;
Node cur = head;
Node prev =null;
Node root = null;
For(int i = 0; i < n/k+1; i++)
{
Node next=cur;
For(int j = 0; next && j <k-1; next=next.next, j++);
Node Temp = null;
If (next){
temp = next.next;
Next.next = null;
}
Reverse(ref cur);
Node head =cur;
If(!root) root = head;
While(cur.next)cur=cur.next;
If(!prev){
Prev = cur;
}else {   prev.next=head; prev = cur;}
Cur=temp;
}
Return root;
}

 

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

We know that the push relabel method indeed terminates because there is a bound on the number of operations it performs. We bound separately each of the three types of operations - relabels, saturating pushes, and non-saturating pushes. With these bounds, the algorithm runs in O(V^2E) time

We now look at relabel-to-front algorithm.

This algorithm improves the running time of the maximum flow problem by choosing the order of basic operations carefully and managing the network data structure efficiently.

The relabel to front algorithm maintains a list of the vertices in the network. It starts from the front and scans the list repeatedly selecting an overflowing vertex u and then removing the excess at that vertex. The push and relabel operations happen as usual in the push-relabel-algorithm until u has no positive excess. On relabeling a vertex, it is moved to the front and the algorithm begins its scan again.

#coding exercise

Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.
If we take the example of 
1. 8, 15, 3, 7  we know that the max value can be 15 + 7
but the strategy of the players cannot be to greedy. For example if player one chooses 8 the opponent chooses 15, player one chooses 7 and the opponent chooses 3 then no player is left with the maximum. Instead the players must use a strategy to minimize the profit for the other.
Given coins laid out from i to j, a player can collect 
F(i,j) = max(Vi + min(F(i+1, j)) ,                        Vj + min(F(i, j-1))
The recursive solution, taking only our turns into account, is therefore 
F(i,j) = Max(Vi + max( F( i+2, j), F(i+1,j-1)) ,
                      Vj + max( F(i+1, j-1), F(i,j-2)))
Int GetCoins(List<int> coins, int i, int j)
{
int n = coins.count;
If (i >= j) return 0;
If (i==j) return coins[i];
If (j == i+1) return max(coins[i], coins[j]);
Return  Max(coins[i] + max(GetCoins(coins, i+2, j), GetCoins(coins, i+1,j-1)) ,
                      Coins[j] + max(GetCoins(coins,i+1, j-1), GetCoins(coins,i,j-2)));
}
int GetBest(List<int> coins)
{
int n = coins.count;
int table[n, n];
int  i, j, k;
for ( k = 0; k < n; k++)
{
   for (i = 0; j = k;  j < n; i++; j++)
  {
     int x = ((i+2) <= j) ? table[i+2, j] : 0;
     int y = ((i+1) <= j-1) ? table[i+1, j-1] : 0;
     int z = (i <= (j-2)) ? table[i, j-2]: 0;
     table[i,j] = max(coins[i] + max(x,y), coins[j]+max(y,z));
  }
}

return table[0, n-1];
}
#puzzle
How many ways can n objects put in k bins ?
The answer is the binomial coefficient n-1 choose k-1
We said we could view this as arranging stars and bars over stars where the bars are analogous to bins that must contain at least one object each and the stars are all lined up with at most k-1 bin partitions between them since there are n-1 gaps, this is equivalent to choosing k-1 from n-1
This is also the number of k tuples of positive integers that form a sum n
If the bins were allowed to be empty, the number changes. Here there can be more than one bin partitition or an empty bin between the stars. We just have arrange stars and bars between them. This is similar to choosing n positions for the star from n+k-1 positions.


This is also similar to choosing k-1 positions for the bar from n+k-1 positions
This is also equal to the number of multisets of cardinality k-1 taken from a set of size n+1.