Storing partial results, Dynamic Programming

Today, I tried to resolve a programming puzzle; which is a bit different than usual problems. Generally a problem like Finding fibonacci series Nth number, has two variants of solutions, Recursive and Iterative. Recursive solutions needs solution for sub-problem first and makes up the complete solution in bottom-up manner.

Fib(n) = Fib(n - 1) + Fib( n -2 )

Ignoring base cases, this would be complete recursive solution. Calculating in this way, would be easier for us to implement, but computation complexity would be huge. For instance, not only Fib(n) calculates Fib(n-2), Fib(n-1) also calculates the same. Same calculations would recur several times. Cause of this is not storing the computed result. For this kind of problems, obvious way to efficiently solve is to store intermediate results. This leads to Iterative solution.

Fib[n] = Fib[n - 1] + Fib[n - 2]

Note: Array is being accessed, not any more recursive function calls. All calculations happen only once.

Computation complexity comes down to O(n). This is one way of viewing Space Time complexity trade off. We successfully traded off space for Time.

There are some problems, don't need all partial results. In that case calculating all the intermediate values would be waste of time. Think about space complexity also.

One such example, taken from CodeChef

One strange bank will provide you three possible coins for a coin of denomination $N, as follows:

$N/ 2, $N/ 3, $N/ 4. N is an integer.

Changing coin would be profitable, for denominations like $12, $24. But for 3, this would cause a loss of $1. (3 /2 + 3 / 3 + 3/4) = $2.

What would be the maximum profit possible with $X.

We can't solve this problem iteratively as we do need result for X, not for 1, 2 ... X. Since X can be considerably big, we can't store all intermediate values also. At last, there is no need for all intermediate calculations for calculating Xth value.

This suggests us to go for Recursion based one. But we know storing intermediate results would help to avoid same calculations several times. So, storing only a part of intermediate results in a Map, or a Hash Table or a Simple array would be very useful.

A Birthday puzzle...

What can be the count of people in a group, given the probability of two people sharing a common birthday?

Let us assume that the correct count is n,

permutation of 365, n => p(365, n) / 365 ^ n = 1/2; Amazingly, the approximate value of n, satisfies this is 23 !!! no way related to the trivial answer 365 / 2 :)

Square root of 2 is irrational.

Proof by infinite descent:

=================

Proving sq.root(2) is irrational is a perfect instance.

Let us say, sq.root(2) a rational number.

x = sq.root(2) . y

x ^ 2 = 2 . y ^ 2 => proves x is even. let us further assume, x = 2 . z

4 z ^ 2 = 2 . y ^ 2 => y^2 = 2 . z^2 => proves y is even.

So, x and y are both even, which can be reduced further and further as proved above. So, x / y, representation of sq.root(2) doesn't exist, and hence irrational.

Identify a running instance - A Software tip

Identifying a running Instance:

Sometimes, It would be very helpful not to start a new instance if another instance is already running. Have your software create a Mutex once it is started and failure to do so, means another instance is already running.

Windows provides Standard APIs to create Mutex, CreateMutex, read through the link below about Mutex Windows API. Obviously, Name of Mutex must be unique and can be magic to avoid unexpected.

http://msdn.microsoft.com/en-us/library/ms682411(VS.85).aspx

Fermat's Last Theorem.

Fermat's Last theorem:

It states an extension of Pythagorean Theorem to higher dimensions is not possible. In simple terms, we can't merge two cubes into a single cube unlike two squares can be merged into a single square. Proving Pythagorean theorem is very simple, but proving Fermat's Last theorem took 350 years until Andrew Wiles successfully proved it. A single proof which almost covers all possible areas of Mathematics, makes this theorem and proof very interesting.

http://en.wikipedia.org/wiki/Fermat's_Last_Theorem