The Simplex algorithm: 

This algorithm solves a linear program -  set of linear equations. It takes a set of linear inequalities and a linear objective function and finds optimal feasible point by the following strategy. 

1. Find a vertex v in the feasible region 

2. While there’s a neighbor v’ of v with better objective value: set v = v’  

A linear equation involving the n dimensions defines a hyperplane when plotted in an n-dimensional space and the corresponding linear inequality defines a half-space, all  points that are precisely hyperplane or lie on one particular side of it. The feasible region of a linear program specified by a set of inequalities is the intersection of the corresponding half-spaces, a convex polyhedron.  

But what do the concepts of vertex and neighbor mean in this general context. Each vertex is the unique point at which some set of hyperplanes meet. 

Each vertex is specified by a set of n inequalities. 

Two vertices are neighbours if they have n-1 defining inequalities in common. 

On each iteration of the algorithm, the simplex has two tasks 

1. Check whether the current vertex is optimal 

2. Determine where to move next 

As we will see, both tasks are easy if the vertex happens to be at the origin. And if the vertex is elsewhere, we will transform the co-ordinate system to move it to the origin.  

When the origin is feasible, it is certainly a vertex, since it is the unique point at which the n inequalities are tight.  

The origin is optimal if and only if all ci <= 0 where ci is the contraint we try to maximize in each dimension 

If all ci <= 0, then considering  the constraints x >= 0, we can’t hope for a better objective value. Conversely if the origin is not optimal, we can improve one of the constraints. 

Thus for task 2 we can move by increasing some xi for which ci > 0. We can keep on increasing it until we hit another constraint. At that point we again have n tight inequalities and hence we arrive at a new vertex. 

For example, given the objective function max 2x1+5x2 

1. 2x1-x2 <= 4 

2. X1 + x2 <= 9 

3. -x1 + x2 <= 3 

4. X1 >= 0 

5. X2 > = 0 

Simplex can start at the origin with inequalities 4) and 5). As x2 is gradually increased, the first constraint is met with equation 3 and therefore it stops at x2 = 3 and the new vertex is given by 3) and 4)  We converge towards the solution in the next step. 

#codingexercise
Double
GetProductNthEveryFourthPower (Double [] A, Double  p)
{
If ( A== null) return 0;
Return A.GetProductNthEveryFourthPower(p);
}

We will resume our book review from previous post shortly but first lets look into

Zero Sum games as described in Dasgupta et al 2006.

We represent various conflict situation in life by matrix games. The schoolyard game rock-paper-scissors is specified by the payoff matrix as illustrated here. There are two players called  Row and Column and they each pick a move from {r, p, s}. They then lookup the matrix entry corresponding to their moves, and Column pays row this amount.

For eg:

                G  =                                                                        Column

	r	p	s
r	0	-1	1
p	1	0	-1
s	-1	1	0

                                                                Row

Let the two play the game repeatedly. If Row always make the same move, Column will quickly catch on because it will play the countermove, winning every time. So Row should mix things up. It can model by allowing row to have a mixed strategy, in which on each turn she plays r with probability x1, p with x2 and s with x3. This strategy is represented by a vector x and similarly Column’s strategy is represented by a vector y.

On any given round, there is an xi, yj chance that Row and Column will play ith and jth moves. The expected average payoff is Sigma(I,j) Gij.Prob(xi,yj) which is equal to

Sum-over-I-and-j (Gij.xi.yj)

Since its Rows gain and Columns loss, Row wants to maximize and Column wants to minimize it.
If Row plays the completely random strategy where xi is each 1/3 and if column plays r, then the expected payoff is the weighted average 1/3*0+1/3*(1)+1/3(-1) = 0 Thus by playing the completely random strategy, row forces an expected payoff of zero, no matter what column does. This means that the column cannot get a negative payoff. Symmetrically, column can play the same and force Row to have a zero payoff.
Thinking about this differently, lets review the following two cases:
First, row announces her strategy, and then Column pick his.
First, column announces his strategy, and then Row chooses hers.
Now we would expect the player going next to fully exploit the known strategy of the first to get the desired payoff. But this is amazingly not the case. If both play optimally, then it doesn’t hurt a player to announce his or her strategy in advance. This remarkable property is a consequence of – and in fact equivalent to – linear programming duality.

(The duality theorem is mentioned this way: If a linear program has a bounded optimum, then so does its dual, and the two optimum values coincide   

To visualize duality, we imagine a string connecting the nodes that is stretched taut. In other words, the dual problem is to stretch s and t as far apart as possible, subject to the constraint that the endpoint of any edge {u,v} are separated by a distance of at most Wuv) 

Imagine a presidential election scenario, in which there are two candidates for office, and the moves they make correspond to campaign issues on which they can focus (the initials stand for economy, society, morality, and tax cut). 

The payoff entries are millions of votes lost by Column. 

G                m             t 

        e         3             -1 

        s         -2             1 

If Row announces that she will play the mixed strategy of x = (½, ½ ), what should the column do ? Since m incurs loss of ½ and t incurs loss of 0, Column should have a pure strategy of (0,1) 

This can be generalized to Pick (x1, x2) that maximizes min (3x1-2x2, -x1 + x2) which is the payoff from Column's best response to x. 

This choice of xi's gives Row the best possible guarantee about her expected payoff. And we 

will now see that it can be found by an LP! The main trick is to notice that for fixed x1 and x2 

the following are equivalent: 

z = min(3x1 - 2x2, -x1 + x2) 

max z 

z  <= 3x1 -2x2 

z   <= -x1 + x2 

and row needs to choose x1 and x2 to maximize this z 

max z 

-3x1 + 2x2 + z < = 0 

x1 -x2 + z <= 0 

3 / 3

x1 + x2 = 1 

x1,x2 >= 0 


Symmetrically we can compose the linear equations in terms of y 

and the critical observation is that these two LPs are dual to each other. 

#codingexercise

Double

GetProductNthEveryThirdPower (Double [] A,Double  p)


{


If ( A== null) return 0;


Return A.GetProductNthEveryThirdPower(p);


}

Today we start the review of a book : "The road to reinvention  - How to drive disruption and accelerate transformation" by Josh Linkner.  Every now and then we lose the momentum from our previous successes and must find ways to make new Successful companies, brands and individuals regularly reinvent their business strategies. This book lays out a systematic approach to continually challenge and reinvent yourself. Either we bring the change ourselves or get disrupted by it. In this book, we learn why we cannot rest on our laurels, the guiding principles for rejecting the status quo and repeatedly reinventing your organization and career for continued success and inspiring examples of reinvention by people who envisioned their futures and soared over competition.
First let us delve into the disrupt or be disrupted part. Hard skills we earned earlier including manufacturing expertise. strong customer skills and even accounting excellence, are now outsourced or allocated to technology. Creativity is the new most effectively sustainable competitive advantage. Therefore change has to be embraced. The author quotes Rupert Murdoch as saying "Big will not beat small anymore.It will be fast beating the slow." Even after making the first leap towards innovation, we fall short of our goals because we think the reinvention is one time. On the other hand, reinvention is a  life long process.
The next step is to differentiate reinvention from turnaround. They don't mean the same thing. Turnarounds are reactionary and shortsighted. By the time turnaround is necessary, it is often too late.
Both these things indicate that we don't want to get to a stage that needs turnaround. Decay like growth does not move in  a straight line.
To embrace the reinvention ethos, we review its eight principles as outlined in the book.
1. Let go of the past - The past is a great teacher, but its a horrible master. Your own grit and determination will become your safety net.
2. Encourage courage - The best organizations focus on celebrating new ideas, instead of punishing them.
3. Embrace failure - "Even bull's eye is the result of 100 misses." adage applies here.
4. Do the opposite -  Sometimes you have to go against the grain for new experiences
5. Imagine the possibilities -  When we get bogged down in the swamp and fighting the alligator, we miss the bank and the forest. Imagine beyond what's visible.
6. Put yourself out of business - This is a way of getting to a point well before the competition does it to you.
7 Reject limits -  The world is filled with nay sayers. Crush supposed limits and refuse to accept the reflexive no
8 Aim beyond - Whether you are launching a product, opening a fashion boutique, seeking a job, or rebuilding a broken community, your focal point must be ahead of you.
Living these principles will develop your innovative muscles.
A good litmus test to ensure you HOSE the competition by delivering new product or service is
1. High Value: Your new product must deliver exceptional value to your customer.
2. Original : Keep your offering uniquely you so it always stands out.
3. Significant:  Go big by breaking the mold of the past.
4. Emotionally charged : If your product evokes passion, customers will line up to buy,
#codingexercise

Double

GetProductNthAlternatePower (Double [] A,Double  p)


{


If ( A== null) return 0;


Return A.GetProductNthAlternatePower(p);


}

Today we continue our discussion with another problem that appeared in Algorithmic Engagements.
Problem statement:

I own a parcel of a polygonal shape. It has 10 sides and its area equals 23 (that is, it con­tains 23 unit squares). The corners of the parcel are: B2, B5, E5, E4, F4, F8, I8, I3, C3, C2, see figure.

Can you draw a polygon with:

(a)    6 sides and area 6?

(b)   8 sides and area 8?

(c)    10 sides and area 10?

(d)   12 sides and area 12?

(e)   14 sides and area 14?

Or a polygon with 13 sides and area 13? All sides of the polygon must be contained in grid lines. Each two consecutive sides must be perpendicular.

Solution:

 The given answer to all the questions is yes and there are quite a few solutions possible for each.
There is no polygon with 13 sides and area 13. Given that every two consecutive sides are perpendicular, the alternate sides have to be either all horizontal or all vertical.
In order for the polygon to bound, we must have equal number of horizontal and equal number of vertical edges. A polygon cannot be formed on a grid with odd number of edges.

The optimal solution can be described in a top down recursive strategy as follows: 

DrawPolygon(W, I, j, numEdges, ishorizontal, startx, starty, totalEdges) 

If I == startx and j == starty  and numEdges == totalEdges

   Return true

if numEdges > totalEdges
   return false;
for delta = -1 and 1
if isHorizontal:

    if (DrawPolygon(W, I, j+delta, numEdges+1, false, startx, starty, totalEdges))
      return true
else
    if (DrawPolygon(W, I+delta, j, numEdges+1, true, startx, starty, totalEdges))
       return true
return false;
}


#codingexercise
Double
GetSumNthAlternatePower (Double [] A,Double  p)

{

If ( A== null) return 0;

Return A.GetSumNthAlternatePower(p);

}

 

Today we discuss another Olympiad problem on Informatics and mentioned by Radoszewski.
Problem Statement:  this is a problem on track siding with an incoming track A and an exit track B - and two auxiliary tracks 1 and 2.

Track A contains 7 wagons numbered 1 through 7. The wagons arrive on track A  in the following order:

(a)    6, 3, 2, 5, 1, 7, 4

(b)   5, 2, 4, 1, 6, 3, 7

(c)    6, 2, 5, 1, 3, 7, 4

(d)    7, 5, 2, 4, 1, 6, 3

(e)   6, 1, 3, 5, 2, 7, 4

The wagons are to exit via track B in increasing order of numbers 1, ...7. Each wagon is to be moved from track A to one of the tracks 1,2 and then to track B exactly once. There can be arbitrary many wagons on each track at the same time.

Can this task be completed successfully? If so, to which auxiliary track should the subsequent wagons be moved?

(For example, if the initial order of wagons was 5, 2, 6, 4, 1, 3, 7 then the answer would be positive. The wagons could be moved using the auxiliary tracks 1, 1, 2, 2, 1, 1, 1 respectively.)

Solution:  The solutions found by trial and error include:
(a) 1, 2, 2, 1, 1, 2, 1
(b) 1, 2, 1, 1, 2, 1, 1
(c) 1, 2, 1, 1, 1, 2, 1
(d) 1, 1, 2, 1, 1, 2, 1
(e) 1, 1, 2, 1, 1, 2, 1

One of the important things to notice is that at all moments, all wagons on each auxiliary track must be sorted in increasing order from the smallest to the highest number  There is a natural greedy approach to this problem but it doesn't always work. For example, we put the next wagon on the auxiliary track where the first wagon has the smallest number. In the first sequence, we should obtain wagons 1,2,3, and 6 on one auxiliary track and 5 in the other. Then if we move 1,2,3, to B then 7 cannot be moved to either auxiliary track. That is the greedy strategy does not work for all permutations. But we can exhaust the search space. One hint provided with this question is that  the subtasks are constructed in such a way that a solution exists. But do we have an optimal substructure? The subtasks are usually increasing order in either auxiliary tracks that can be moved out to B. However, the order need not be strictly consecutive. And it is better to utilize more and more auxiliary tracks when the subsequences cannot be consecutive or increasing.
Therefore there are really three moves possible for a wagon
Move(wagon):
If a wagon can go directly to B from auxiliary tracks, move it to B
If a wagon can go directly to B from A, put it in auxiliary track 1 and move it to B
If a wagon has to go into one of the auxiliary tracks and not to B then
        pick the one which has a consecutive higher number. (or if its distant by less than half of the total length of initial wagon set - so as to increase the likelihood of encountering a further number that can start a new stack)
        pick the one which is empty
        pick the one which has a higher number

The third step above should be simplified to pick the auxiliary track which has a higher number. The refinement above helps in quicker convergence.
Generally these moves accumulate the wagons on the auxiliary track until the first wagon reaches there.

Backtracking works here because it never considers an invalid option (a wagon moving over a lower numbered wagon on the auxiliary stack) and reduces the number of options from the permutations. We can choose one of the two auxiliary tracks as possible choices. The size of the auxiliary track does not matter so long as the wagons can be put in the order mentioned above. The termination conditions are when the next wagon from A does not have an
auxiliary track to be put in and when the wagons in A have been exhausted. The recurrence is based on the either auxiliary track receiving the wagon or the wagon exiting to make space for a
new wagon from A.

There are alternate solutions possible too such as where we don't check for each move but at the end of a sequence. For example,
we could think of each wagon getting an end result of 1 or 2 as the auxiliary track to use. Hence the entire sequence is a permutation and combination of these two choices. And for each sequence generated we can test whether it is valid or not with some bailing quickly than others. The generation of permutation is discussed earlier in this blog.

 

 

 

This is a problem that appeared in Algorithmic engagements 2007 and discussed by Kubica and Radoszewski 

The problem statement: 

An anti-binary set is a set of integers that does not contain two numbers of the form m and 2m. For example, the set: 

A = {2, 3, 5, 8, 11, 13} 

is anti-binary whereas the set: 

B = {2, 3, 5, 6, 8, 11, 13} 

is not, since both 3 and 6 are its elements. 

What is the largest size of an anti-binary set that is a subset of 

1. {1, … , 11} 

2. {1, … , 12} 

3. {1, … , 13} 

4. {1, … , 14} 

5. {1, … , 15} 

How many different anti-binary subsets of the same size exist? 

The Solution: 

In this case a graph like this helps: 

1 --> 2 -->4-->8 

               3-->6-->12 

                5-->10 

              7 9 11 13 

Where --> denotes an edge when elements are connected by the relation m-->2m 

The elements that don’t connect are mentioned last. 

We can select all of the elements in the last row, one element from the second last row, the first and the last element from the second row and alternate elements from the first row giving us the cardinality of 9. 

More generally, let us say that for a path of size n, the number of anti-binary subsets is An. Then the number of all anti-binary subsets of the given sequence is A1 power 4 times A2 power 1 times A3 power 1 and A4 power 1 by permutations. A1 = 2 and A2  = 3 because we say whether those anti-binary element or its combination is included or not. 

Since the pattern of picking the anti-binary set is that of picking alternate elements in the series m[Symbol]2m, we say that if an anti binary set contains the last element, it does not contain its predecessor.  Hence the number of such sets equals An-2. Given that the last element can be included or not, we establish an optimal substructure as An = An-1 + An-2 

And hence a recursive relation where A1 = 2 and A2 = 3. 

This therefore is the Fibonacci series where An = Fibonacci(n-2) 

int Fibonacci(int n)  {  

if (n <= 0 ) return 0; 

 int value = Fibonacci(n-1) + Fibonacci(n-2);  

return value;  

} 

And we can count all the subsets as follows: 

AllAntiBinarySets(A, n)  

If n == 0   Return 0  

q = 1  

int r = n %2 == 0 ? n: n+1 

For k = I to log(r) 

     If (graph-exists(A,k)) 

            q *=  Fibonacci(k)*numberofGraphs; 

  return q