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.

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, et.al. 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"
a=input()
print "Input the next number to be multiplied with %d" %a
b=input()
res=0
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

Balbir's log - 27 Feb 2007

1. Played around with Scilab, used scilab for some simple signal processing work, Amplitude Modulation.
2. I've started reading a paper on VM entitled Making LRU friendly to weak locality workloads
3. Added Markov chains to my to-learn list

Using maxima -- baby steps

The use of symbolic computing makes it easy to visualize and solve problems that were otherwise dry and would put you to sleep. To test the simplicity of a freely available tool called maxima, I tried to solve a common problem with it.

The problem is quite simple, remember high school physics? Well I don't :-). Consider a tuning fork, which oscillates and produces a sound (depending on it's frequency).

We start by entering the mathematical model of the fork

'm*diff(x(t), t, 2)=-k*x(t);

Maxima prints


We now request maxima to solve the equation for us by

desolve([%],[x(t)]);

Maxima asks

Is k * m positive, negative, or zero? We say positive

Maxima prints



We ask maxima to simplify the result for us

radcan(%);

Maxima outputs



That's it, we have our solution.

What have I been upto?

I've spread myself quite thin, with a lot of code to write, books to read, things to buy and documentation to write.



For now, I have started reading Structure and Interpretation of Computer Programs. I've started reading it, don't skip the foreword or the preface. Be patient with the author and go read it, it's fun!

Meanwhile, I hope to get back to productive coding soon, instead of just reading hundreds and hundreds of papers.

One of the hardest problems software faces today

I think the biggest problem is to get users to read the documentation associated with the software.

Try answering these questions and score yourself.

1. How many times have you seen a question about a problem being repeated?
2. Why do you they created FAQs?
3. How many FAQs have you read?
4. What was the last release notes you read?
5. Which book did you read last (not related to your course)?
6. What new techniques did you read and discover in the last two years?
7. What kind of documentation did you write and share for your last project?
8. What was the last software manual you read?
   
9. What was the ratio of comments to code in

• Programs you wrote
• Programs you read

The answers to these questions might not be a simple yes or no, but it will give you a fair idea of how we programmers are lazy and totally ignore documentation.

Some pictures from our New year and Lohri celebration (A Story!)

Me and my gorgeous wife before we left for the new year party

I sparked off the Lohri celebrations

Popcorn and Peanuts in fire
A Lohri ritual

The flames got higher, lohri had now begun

Ritual walk around the fire

The crowd got bigger as the flames got higher

My brother enjoyed the heat

My in-laws got involved as well
(My brother-in-law, his wife and son)

I had to keep encouraging people

The last round

There was only so much firewood!

It was time for dinner
(The chef was ready!)

Dinner was served, the food was awesome!

My wife's nephew, he came, he saw

He bowed!

Happy Lohri

Mufli ki khusbu, gurh ki mittaas
Makki ki roti aur sarson ka saag
Dil ki kushi aur apno ka pyar
Mubarak ho apko Lohri ka thyohar!

If the whole thing bounced over you, see http://www.lohrifestival.org/. We are celebrating our first Lohri

Article: A Conversation with John Hennessy and David Patterson

Read A Conversation with John Hennessy and David Patterson published in ACM Queue. It's one of the best articles, I've read lately. They talk about the challenge with parallelism, the free ride software has had, their new book, new projects and much more.

I highly recommend reading the article

It's prediction time!

It's come a little late this year, but here goes anyway. The list includes technology, business and other predictions for the year 2007

1. Apple will go back to using the PowerPC
2. Intel will gain an upper hand over AMD in the 64 bit space
3. Microsoft (R) Vista (TM) will not be widely accepted, people will expect too much from it
4. Internet Explorer 7 will do well, but will begin to loose out gradually towards the end of the year
5. India, Dravid, Chappel and Tendulkar will have a rather forgivable (we'll loose out before the semi-finals) world cup
6. The world will get ready to move to 128 bit computing, there will be rapid growth towards 1024 bit computing machines
7. Adobe, Google and Apple will continue to do well
8. Open source movement will slow down for this year

These predictions are not very scientific, they are based on gut feeling. Feel free to comment on any of the predictions. I'll try and keep the list up to date or add your predictions if I really like them

Have A Great New Year!

Let's all welcome the new year with a big smile! I hope it turns out to be a great year for us, our families and friends, and all of mankind. There are so many things to do, so let's get started!

Quote of the Day

The creation of standardized, vendor-independent operating systems, such as UNIX and its clone, Linux, lowered the cost and risk of bringing out a new architecture

David Patterson and John Hennessey

A shortcut through time

Written by science writer George Johnson, this book talks about mans quest for the ultimate computing machine, the Quantum Computer.


The books begins with the basic of computing, the language used is quite amusing

"In a typical circuit, there were resistors that, true to their calling, resisted electricity, pinching the flow of electricity"

The book starts off with the authors experience with GENIAC, a mock clone of ENIAC. The author then explains, tinkertoy logic, the book helps the reader discover that computers are more about logic, more than semiconductors that are used to build them. Logic is more important than how it's actually implemented.

The book then dwells into physics, explaining how atoms spin, and how depending on the direction of spin, we can treat the spinning as a boolean quantity as 1, 0 or Φ. Φ represents the state of the atom, when it is spinning in both directions simultaneously.


The introduction to Quantum physics makes a good read and makes me wonder why I slept through Physics in school. Reading further through the book the author aptly states "Human brains are just not equipped to intuitively understand the subatomic rules". The author then takes you to the Aha! Moment, when you realize that the Quantum Computer is so powerful that it can carry out 2ⁿ computations simultaneously, where n is the number of computing bits.

The book then introduces the layman to the Turing Machine and computational complexity, followed by Cellular Automata, Shor's Factoring Algorithm and its application to the world of Quantum Computing. No mathematical proofs are included in the book, but the concepts are well illustrated with examples and supporting diagrams.

Cryptography is then introduced along with the challenge of decrypting code, the computational complexity of cryptanalysis and implications of a quantum computer on current security technology is discussed.

What follows is an elegant description of logic gates and reversible logic. The current and state of the art attempts made at building a quantum computer are described in detail. Quantum error correction, its need and challenges is also discussed.

The book closes with chapters on Quantum secrecy and describes how polarized photons are used to implement quantum cryptography. Real life examples of hard problems, like protein folding is discussed. The reader is introduced to the fact that protein folding is a hard problem to solve (see books on NP-Hard) and the mystery surrounding how nature is able to solve the problem so quickly is discussed.

In summary, this is a great book to read. If you know and understand computer science, it will expose you to how, some of the most complicated concepts can explained without the need for complex mathematics. If you do not understand Quantum computing, the concepts exposed will get you interested in the world of Quantum, where the laws of nature are different. Simple Newtonian physics cannot explain what goes on inside an atom. It is this randomness and uncertainty that can change the way we compute today.

Just my lucky day! (errata in The METAFONTbook)

I got this email as a reply for an errata report I sent out

thanks for your report.

I hope I am emailing the correct people for an errata I found in The MetaFont book Volume C, Page 159

yes. you've come to the right place.

Original Text

For example, Appendix B says

def --- = .. tension infinity.. enddef .

Corrected Text (It should be)

For example, Appendix B says

def --- = .. tension infinity .. enddef;

(Note the change from . to ;)

i've verified this; the reference in appendix b
is on p.262. i don't see any earlier reports on
this, so it looks like you're the first.

should this actually be the case, you will be due
a small reward. to deliver it, we'll need a
postal address. i've received word from knuth
that he expects to be looking at reports about
this time next year, so an address that will be
current at that time is what we'll need.

-- bb

Update: Balbir's Blog: Problem 4.2 Page 85, Introduction to Algorithms

I posted an entry about a possible errata in Introduction to Algorithms at
Balbir's Blog: Problem 4.2 Page 85, Introduction to Algorithms

Well, it's a part of the errata of the book now. Check out http://www.cs.dartmouth.edu/~thc/clrs-2e-bugs/bugs.php the errata reads

Page 85, Problem 4-2. Change the second paragraph of the problem to read, ``Show that if the only way to access information in array A is by this single-bit operation, we can still determine the missing integer in O(n) time. Any entire integer outside of A is still accessible in a single operation.''
Reported by Balbir Singh. Posted 29 November 2006.
Severity level: 3
To be corrected in the eighth printing.

Severity level 3 is "A more significant technical or expository error"

I have not yet figured out how the new solution works (with the new constraint), if anybody else thinks of it, please do comment on it here.

Is Dravid headed down the Ganguly lane?

© Getty Images

An indifferent performance at Durban (a place with a good amount of Indian support) and in his last dozen matches, is Dravid headed down the Ganguly lane? Is captaincy and planning leaving no time to play and enjoy the game. Is the politics of Indian cricket along with the six thinking hats of Greg Chappell getting too hot for Rahul?

I for one am very skeptical of the Indian batting line up. Sehwag is too adamant to listen to anyone - that's his natural style right? Tendulkar, the poor guy sees everyone getting out and goes into a shell (and gets out!). Kaif and Yuvraj, have no technique while batting. Give them a venue that supports swing and they'll lollypop their wicket to the slips. Dhoni might be ranked high, but it's a miracle when he manages to play the ball where he intends to.

Let's not even discuss the tail-enders

Whenever India comes in to bat, nobody can predict how well they'll do? They are prone to collapsing, known to be panicky and have the killer instinct of a Sparrow. The one thing they are good at is acting, look at their advertisements and you'll see that all of them can almost act. May be the BCCI has an acting academy inside the sports complex.

Is the wall wearing out? I hope not to give up so soon, but I am very frustrated.
I am going to protest, not by not watching the cricket matches, but by not purchasing anything advertised by an Indian cricketer.


How's that???? (If the umpires are looking at this blog :))

Problem 4.2 Page 85, Introduction to Algorithms

Here's my first post that's actually a PDF article. It contains a lot of math and I thought it would be best to convert it to PDF and then post the link here.

Comments on Problem 4.2, Introduction to Algorithms

Enjoy!