Saturday, March 24, 2007

Reserving space for my good bye to the Indian Cricket Masters

Dravid, Ganguly, Tendulkar should go now! Dravid and Tendulkar must go for sure and so should Mr Greg C. Let's see how the Indian team responds to this defeat.

Thursday, March 01, 2007

Balbir's log 1st March 2007

  1. Read a very interesting algorithm called the Ford-Johnson method for sorting. I ended up opening Knuth's Volume 3: Sorting and Searching and reading through his quite amazing illustration and explanation of the method.
    • References - Don Knuth, vol 3, 3rd Edition, Page 184
    • Horowitz and Sahni, Fundamentals of Computer Algorithms
  2. Read through the introduction in the Algorithms book by Papadimitriou, See my post on a fun way to multiply numbers
  3. Played around with the python programming language after a big break

Follow up: A fun way to multiply numbers

Here's python code to multiply numbers as mentioned in the A fun way to multiply numbers blog entry.

NOTE: I am not a python expert, so there could be some obvious bugs in this simple piece of code. As always use at your own risk.

print "Input the first number"
print "Input the next number to be multiplied with %d" %a
while a:
if a & 0x1:
res = res + b
a = a >> 1
b = b << 1

print "The result is %d\n" %res

A fun way to multiply numbers

Reading through the algorithms book by Papadimitriou, et. al has been great fun. I learn a great fun way to multiply (apparently known from ancient times). Let's say we intend to multiply 13 and 23, the procedure is quite straight forward. Write down 13 and 23 besides each other
13 23
6 46
3 92
1 184

The first column is divided by two (with rounding) and the second one is multiplied by two

13 23
6 46
3 92
1 184

Strike out the numbers with even numbers in the first column

Now we just add up the numbers in the right column to obtain 299. That's quite easy right? The really cool thing about this approach is that is easy to implement using computers (hint: left shift and right shift multiply and divide the number by 2 (with rounding taken care of))

Balbir's log - 28th Feb 2007

  1. Freshly installed FC6 - 32 bit edition, still in the process of setting it up (another blog entry). I hope to get KVM and UML running
  2. Played around with Linux's Connector interface (kernel <-> user communication)
  3. Read through chapter 5 (partially) of Computer Systems Performance Evaluation and Prediction

Dynamic programming for the binomial coefficient

More fun things, this time with some visualisation of what happens when memoisation is used and what happens when we don't. I don'...