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