The Smart Trader (Algorithm 2)

Points : 13

In medieval period both forms of exchange namely barter and monetary were allowed. Barter exchange was limited to certain precious items only like gold, silver and other precious stones.

A smart trader used this to his advantage. He initially had some gold with him. Later he exchanged that gold with ruby stones (1g of gold buys 0.6g of ruby) and then exchanged his ruby stones with silver (1g ruby buys 3g silver) and then further exchanged silver with gold (1g silver = 0.60g gold). Consequently he has made a profit of ( (0.6 x 3 x 0.6 = 1.08) - 1 )= 0.08 per gram of gold.

As it happens to be the rule of barter system, he has to exchange the entire weight of the stone he possesses during each transaction. Also he can exchange one stone for another only once during the entire process.

Suppose there are n stones(s1,s2...sN) and a table(C) n x n of exchange rates between them such that one unit of s1 buys C[1,k] units of sk.

Given this, write an algorithm for the order of exchanges the trader should make to avail maximum profit if he starts with stone s[m] and he has to finally end up with the stone he started with.

Also, explain the time and space complexities of your algorithm.

Solution

Given: R[N][N] : matrix of exchange rates. s[N] : matrix of stones s0...sn

Let: P[N][N] : a matrix that stores maximum profitable path so far. There can be at most n exchanges starting at stone s[0]. Let, P[i][j] represents the maximum profitable path till jth transaction which ends at ith stone

Let allowed_state[N][N] represent the allowed states for exchange from column j in P.
e.g if allowed_state[j][1] == 1, an exchange to stone s1 is allowed from column j
Without loss of generality it can be assumed that s[0] is the starting stone.

We use a dynamic programming approach as follows.

//Initialize the first Exchange
//fill the column-0

  P[i][0]=R[0][i];
//update allowed_state
allowed_state[i][i]=0;
   

//Carry on the later exchanges

   for every column j from 1 to n
   {
      // j-th exchange

 	for every row i in that column
      {
      // i : the final state after this exchange
                 // consider every element of previous column.

     	   // if exchange to i is allowed, check profitability
         
       for every row k in previous column
	 {
            if (allowed_state[k][0] && allowed_state[k][i])
	      {
	        if ((value = P[k][j-1]*R[k][i]) > max_so_far)
	        {
                 max_so_far=value;
		     selected=k;
	        }
	     }
	 }
         
// max_so_far will contain the maximum product path so far.
// selected contains the previous state from which path to i is selected.
// set P[i][j] with maximum profit transaction
	 
       if ( selected == -1)
	 {
           P[i][j]=-1;
	   continue;
	 }

	 P[i][j] = max_so_far;

 // update allowed state for i
// new allowed state for i :  allowed_state for selected - {i}

	 for (int k=0; k< n; k++)
	 {
	   allowed_state_tmp[i][k]=allowed_state[selected][k];
	 }

	 allowed_state_tmp[i][i]=0;
	 max_so_far=-1;
	 selected=-1;
      }  
     copyMatrix(allowed_state_tmp,allowed_state,n);
// allowed_state updated
// Repeat for next exchange
}

Maximum Profit transaction = max of row P[0].
An auxillary matrix can be used to trace the path of exchanges.

Complexity

Time: O(n^3) : filling every entry (n^2 entries) of matrix P in O(n) time each.
Space: O(n^2) : for allowed_state

Post your queries at the CodeWarrior forum thread Round 1-The Smart Trader (Algorithm2)