Remembering Ohm's law

Came across this beautiful way of remembering Ohm's law V = I*R.

Arrange the letters in the form of a triangle as follows. It is as if the area of the triangle has been divided into 3 areas each represented by V, I and R.

V
- - -
I | R

* To obtain the formula for I, just cross out I from the figure and you are left with V/R.
* To obtain the formula for R, just cross out R from the figure and you are left with V/I.
* To obtain the formula for V, just cross out V from the figure and you are left with IR.

Nothing special really, but I think it's beautiful !:)

Infact, this arrangement could be used to represent any equation of the form A=B*C.

Josephus Problem

I decided to give this one a try. I knew that there exists an algorithm to solve this problem but it is more fun to try, fail, then try once more, fail again and then pounce on the known algorithm when the suspense becomes unbearable !:D

The simplest idea that comes to mind is to create a circular singly-linked list from the numbers and go on deleting the nodes, which is quite a violent activity actually, since it is equivalent to killing the people in the circle !!:D. So the next time you decide to delete a node, think twice :P

Anyways, this algorithm though quite simple is probably overkill for the problem and involves linked list manipulations. Equivalently, an array may be used as well, where the killed soldiers are marked by a special entry in the array.

Then, I had a glance at the algorithm and noticed that it doesnt use arrays or linked lists. I decided to give this approach a try.

But the question was what to track ? Do I track the last number that was deleted or the last number remaining after a round of deleting numbers from the array ?

(more coming soon ... )

Card Trick - Declaring the Nth card

Split a deck of cards into two halves, say H1 and H2. Select any one half, say H2 and lay down all the cards face up one-by-one. Then pick them up without disturbing the original order and place them below H1.

Now, hold the deck so that the cards are facing down.
Draw the first card from the deck and place it face up. If it is any one of K,Q or J, consider it equivalent to a 10. The idea is as follows:

Let the card be 'x'. Now count from 'x' upto 10 and for each number in this count, draw a card from the deck and place it face down on 'x'.

Repeat the above procedure for two more cards, say 'y' and 'z'.
Now, let N = x + y + z.

Say that the Nth card in the remaining deck of cards in ur hand is so-and-so and then hey presto ! The Nth card is indeed what you said it would be.

Trick:
------
Initially, when you are the putting down the cards from one of the halves, remember the 7th card.

Logic:
------
Let the cards that are put down be x, y and z. Consider a card x. You draw cards from the deck and place them on x until you reach 10. That is, if the card is x, you draw (11-x) cards from the deck including x.

So initially, you draw (11-x + 11-y + 11-z) cards from the deck. Then, you draw N more cards from the deck where N = x + y + z.

Hence, in toto, you draw ( 11-x + 11-y + 11-z + x + y + z ) = 33 cards from the deck.

If you know the 33th card, you are done ! That is why, initially you lay down one of the halves and remember the 7th card and then place this half below the other.

So go ahead and take the second step in becoming a magician. The first one is ofcourse growing whiskers and acting strange and mysterious about anything and everything !!:D

Non-recursive tree traversals

Was asked recently by a friend to try this out. They are all almost the same except that postorder is a bit tricky. And do drop a gentle and kind comment if there are any mistakes :D

So here goes ...

Inorder:
--------
inorder(node *ptr)
{
  lptr = ptr;
  while(lptr!=NULL) {
    stack.push(lptr);
    lptr = lptr->left;
  }

  while(!stack.empty()) {
    p = stack.pop();
    print(p->data);

    q = p->right;
    while(q!=NULL) {
      stack.push(q);
      q = q->left;
    }
  }
}


Preorder:
---------
preorder(node *ptr)
{
  lptr = ptr;
  while(lptr!=NULL) {
    print(lptr->data);
    stack.push(lptr);
    lptr = lptr->left;
  }

  while(!stack.empty()) {
    p = stack.pop();
    q = p->right;
    while(q!=NULL) {
      print(q->data);
      stack.push(q);
      q = q->left;
    }
  }
}


Postorder:
----------
postorder(node *ptr)
{
  lptr = ptr;
  while(lptr!=NULL) {
    stack.push(lptr);
    lptr = lptr->left;
  }

  while(!stack.empty()) {
    p = stack.pop();
  
    if(p->right==NULL || p->right==last) {
      print(p->data);
    }
    else {
      q = p->right;

      // if right child exists, push back the parent node onto the stack
      if(q!=NULL)
        stack.push(p);

      while(q!=NULL) {
        stack.push(q);
        q = q->left;
      }
    }
    last = p;
  }
}

Fibonacci numbers

I came across three algorithms to compute the nth Fibonacci number. The last one is beautiful :)

(1) Recursive algorithm (exponential time)
(2) Non-recursive algorithm (linear time)
(3) Algorithm based on the usage of matrices (logarithmic time)

For details, refer http://en.wikipedia.org/wiki/Fibonacci_number

First post

Hello world !!