Recursions to Non Recursions

Recursive routine

<type>funname0(para1, para2,...)
{
Code1;
if (cond1)//termination condition
{
Code_if;
return value;
}
Code2;
p = funname0(t1,t2...); //1
Code3;
k = funname0(p1,p2...); //2
code4;
return val;
}

Non Recursive Routine
<type>funname1 (para1, para2,...)
{
<type>extra;
/*
define stack with (all the data, which is visible to any of the recursive call)+
int funno(say)(signifying the which call has pushed this data );
*/
while(true)
{
while(true)
{
{All data declaration}
Code1;
if (cond1)//termination condition
{
Code_if;
extra = value;
break;
}
Code2;
// all pre operations(in call) should be done here //1

//Push all the data that is visible to any successive recursive call //1
//push 1 to funno
para1 = t1;
para2 = t2;
...
}
if(!stack.empty())
{
//pop out the values from stack to corresponding variables //1
switch(funno)
{
case 1:
p = extra;
// all post operations (in call)should be done here //1
Code3;

//all pre operations(in call) should be done here //2
//push all variables into stack, visible to any successive recursive calls //2
//push 2 to funno
para1 = p1;
para2 = p2;
...
break;
case 2:
k = extra;
// all post operations (in call)should be done here //2
code4;
extra = val;
break;
default:
}
}
else
return extra;
}
}


Find a elment in Matrix

Hey new question has occupied me this time, the question is like:
"We have matrix with rows and columns are sorted independently. And we are now asked to get some particular element"

One of the solution of this problem is assumed by taking a middle element to test and then proceed like binary search algorithm.
But.....
You know it will not have the same O(log n) order where n is matrix order as the case with usual binary search.

You my easily conclude that the complexity function with input size "n", can be defined as:
T(n) = 3*T(n/4) + constant

And by master method the complexity comes out

T(n) = n ^ (log43) = n^(1/4) = o(log n)

Ohhhh what happened!!!
I think its quite obivious as when you partition a space into 2 of which only one is to be searched which again be halved. But in this case you have partioned into 4 out which in worst case you may need to search in 3 spaces.
The beauty of getting order log n is not in saying that one part does not have the answer, but is in saying that the answer lies in only one partition.

Minimum Weights to Calculate all

Find the minimum no. of weights and there weighing, needed to evaluate all the weights from 1Kg. till some weight let say 243 Kg, with integral multiple of 1Kg.
Lets workout for the objective...

The statement in concern is similar to –“Create each no. between 1 to 243”

Since we know that a number system is capable of doing so, thus any number system can build such a family to weigh all the weights between any two weights.

Like if we have weights:

1, 2, 4, 8 … or

1, 3, 9, 27 … or

1, 4, 16, 64 … etc.

We can weigh each weight between

Now a big question how can we create each and every weigh with any one of these combinations.

*Thus we need (k-1) no. of each weight for k base option.

Thus total no. of weights used in first case for calculating 1 to 10 Kg.

= 1(1Kg) + 1(2Kg) + 1(4Kg) + 1(8Kg) = 5

And in 2^nd case no. of weights used for calculating 10 Kg

= 2(1Kg) + 2(3Kg) + 1(9Kg) = 5

For generalizing the question, if we take k-base family of weights for calculating 1 to n Kg. We need floor (log _k n) no. of different weights.

Cost associated with using different kind of weights = floor (log _k n).

And number of weights needed of a particular measure is (k-1).

Then weights used are, f(k) = floor (log _k n) * (k-1)

So, for particular n we want to minimize f (k) = (k-1) * floor (log _k n).

Assuming f (k) = (k-1) * log n / log k

k-1/ log k is an increasing function for all k > = 2.

Thus f(k) is increasing function for all k >= 2, thus has a minima at 2

But our function is discrete and may not behave as we assume, but for sufficiently large “n” information stored in bits “binary digits” is cheapest as compared to any other number system

(****if some body needs the plot of graph pls. comment here your mail id so that i can mail you)

But incase of balance we can put weights at either side.

This actually maps the situation like that putting a negative value of same magnitude at any position does not actually contribute to additional cost.

So the cost, g(k) = ceiling ((k-1)/2 ) * ceiling(log _k (n)) , k > 2

g(k) = g(k) = ceiling ((k-1)/2 ) * floor(log _k (n)) , k = 2 (as there is no need of putting weight onto other side of balance)

(****if some body needs the plot of graph pls. comment here your mail id so that i can mail you)

This very much clears the doubt that now 3 base weight family out performs anything.


**One more notable thing is that in base 3 family weights, any combination of weight will correspond to a net weight which can not be weighed in any other way. This also assures that this has minimized the no. of weights.

But this also arises a question in my mind:
Do we have no other way of representing numbers without any number system :)
Well for now thats it....
Soon will write more!!