Find the name ‘12345’

Yandamoori Veerendranath is one of my favorite authors of Telugu literature. In his novel “Vennello Adapilla” a fantasy story, the female character teases the male character. She makes a puzzle out of her name and challenges the hero to crack it, ofcourse he cracks it in few moments. It is goes something like,

“The name consists of five English letters. Put 26 dots on the paper each dot corresponds to each letter of English language. The name ends at the dot where it starts. What would be my name?”

With the inspiration of the above puzzle, a Telugu song from the movie “పల్లకిలో పెళ్లి కూతురు” was written, it was composed by Keeravani. The name mentioned in song is Raani. The answer to above puzzle is also near.

Horse Race

June 22, 2010

The following question is on races, similar to the previous post…

The tricky question, given 25 horses of different caliber, intent is to find best 3 horses in minimum possible number of races under the constraint that only 5 horses are allowed per race.

We can generalize the question as, set of N² horses and allowed N horses per race. How many minimum races are required to find best 3 horses?

Hint: Generalisation has the clue. You need to be aware of matrix optimization techniques. Also try, how to find 4^th best horse?

Find the second element

June 22, 2010

How can we find second best player in a tennis tournament? In other words, how can we find second largest element in an unordered array? Assume that the array is having all distinct elements. What is the affect on algorithm if the array contains duplicates?

In most of the standard text books on algorithms, we can see solution to the above problem. There are various ways; each method has its specialty in different scenarios.

Hint: Keep track of players/elements. Explore various methods of book keeping.

Bit Reversal

3^rd June, 2010.

In Embedded Systems Programming, it is often required to reverse bits in the machine word (it can be of any length). Usually in desktop programming we will have high speed processors that operate in the order of few Giga Hz. Where as in embedded systems such as cell phone the core operates in the order of hundreds of Mega Hz. Hence, every byte and every instruction is counted for best optimum algorithm. Note that computing power is not determined by processor speed. We have Param Padma super computer constructed on 630 nodes (processors) operating at low frequency.

It is important to select an optimum algorithm than playing with tricks. Further optimization can be achieved by fine tuning the algorithm implementation. A bit reversal would be required in places such as Fast Fourier Transform in implementing DSP algorithms. Here is algorithm to reverse bits of 32 bit word,

• Swap adjacent bits in the word, i.e. bit position pairs are (0, 1), (2, 3)…(28, 29), (30, 31).
• Swap adjacent 2 bits in the word, i.e. bit position pairs are (01, 23), (45, 67)…
• Swap adjacent 4 bits in the word
• Swap adjacent 8 bits in the word
• Swap adjacent 16 bits in the word

It can be done in log(32) = log(2⁵) = 5 steps. It is analogous to binary search algorithm. Similar technique can be used to count number of 1 bits in the word. Try it.

Dropping a Ball

1^st June, 2010

The puzzle is from famous puzzlest Sam Lyod.

A ball is dropped from building of 100 m height. The ball bounces 10 % of previous height due to Earth reaction. Question is how long the ball traveled before ceasing its motion?

If you get the answer as [h + h/10 + h/100 + h/1000 + so on], you have a lacuna in the problem understanding.  Because except the first instance, the ball travels twice the distance of drop height. The solution fall into G. P. of infinite series. The answer is 122.22 m. Try it.

Here is a hint,

S(n) = h + h ² + h ³ + h ⁴ + …

h x S(n) = h ² + h ³ + h ⁴ + …

After simple subtraction we get the following simplification for S(n)

S(n) [1 – h] = h ==> S(n) = h/(1-h)