August 23, 2010

Interesting Problems

The Hershey Bar problem:
Give an optimal algorithm to break an mxn Hershey bar into 1x1 pieces. At each step, you can choose a single rectangle of chocolate and crack it along one of its vertical or horizontal lines. A single crack counts one step. You are to make the fewest number of cracks.

David Gries's coffee can problem:
Given a can of black and white coffee beans, do the following: Pull out two beans: if both are the same color, replace them with a white bean. If the two are different, replace them with a black bean. What color is the last bean?

August 15, 2010

The Common Feature Among All Living Beings

What is pain?

Is it a feeling? (If so, what is a feeling?) Is it absolute? What makes it different between us, a crocodile, a tree, a microbe? Does a microbe really feel pain?

Is pain really a good thing or a bad thing?

I think one thing common among all creatures is the pain. Whether it is a feeling or inter-cellular reaction chemical reaction or inner-cellular or whatever. It seems to be existent among all living beings.

It is the sense of pain that causes a living being to continue living. I am definitely sure of myself that I didn't feel pain, I wouldn't have lived until now.

August 13, 2010

Distribution of Factor Count for Numbers

I extracted the frequency of the factors for numbers in the range [2,  10^6]. It was quiet interesting for me. Why is it that 2,688 numbers have 30 unique factors but there are ZERO numbers that have 32 factors?

While studying about randomized algorithms in wikipedia, one of the very first algorithms in this context is the Miller-Rabin primality test and an important statement in their algorithm is that:

"If n is composite then at least three-fourths of the natural numbers less than n are witnesses to its compositeness."[1,2]

But a number like 22 has only two numbers are witnesses of its compositeness (2 and 11). So what does that mean. I thought that it could be true for most numbers if we get to infinity, therefore I counted the number of factors (witness of compisiteness) of the numbers from two to one million. And as the mubers grow their factor count become less comparable to their magnitude. So what does that quote mean?

[1] .
[2]. Dietzfelbinger, M. and Hagerup, T. and Katajainen, J. and Penttonen, M. "A Reliable Randomized Algorithm for the Closest-Pair Problem", Journal of Algorithms, Vol 25, Issue 1, 1997.