Negative Binomial Coefficient

While reading through a book on probability and calculating the expectation of geometric series, I came across an interesting sum
We know that if then the sum converges to


Coming from the other side and using binomial theorem we getwhich expands to



Which leads to an interesting conclusion

I got maxima to verify this by calling the binomial function for various combinations of -1 and n. I am a little confused about the interpretation of the meaning though

Usually nC2 is used to imply from "n" objects, choose 2 at a time. nC2 gives us the number of total such combinations. What does -1Cn mean? What are the other proofs for -1Cn?

MUST READ: The Last Lecture

I first heard of the book when I was traveling to a conference with a colleague who wanted to read the book, but wanted to find the best place to buy it. He briefly mentioned what the book was about, which I quickly forgot. I saw it again at several places, until I finally bought it from Strand bookshop in Bangalore. The most famous quote from the book is

“We cannot change the cards we are dealt, just how we play the hand.”
--Randy Pausch

This is one of the few books that I've had several people in my family read partially and love it (they are waiting to finish the full book). The book is about childhood dreams, how to achieve them and also goes a step further and talks about how to help others achieve their dreams.

The book is spectacularly well written, when you begin feel sad for Randy (the Author), there is a twist that will make you feel proud of the way Randy handled himself. The book is about positivity, about never giving up, about believing in humanity, in being true, about family values, about the good in the world, with sometimes what cannot be controlled and must be accepted.

Don't pick this book up as a pity book for Randy, you'll be left pitying yourself after reading everything that Randy did and how he lived his life, leaving us pondering if we've made the best use of our time. Randy focuses on family values, his students, his mentors, his family and there is not a single negative sentiment that he passes on to the readers.

If you are feeling depressed or need something good and small to read, something to boost your moral, to rebuild faith, to appreciate life and the people around you, you must read "The Last Lecture"

Dhoni's belief in Dravid

I like Dhoni's attitude, he said two important things

1. Demoting him will put pressure on him, since 3 or 4 wickets would have fallen when he comes in
   
2. He is a good player, who needs some time in the middle
   

That is again a sign of good captaincy. Dravid, wake up, shake up, cricket calls!

FOSS.IN (part 2)

In continuation from FOSS.IN (part I)


Photo by Sony Phil

The first keynote was from Harald Welte. The keynote was about embedded devices, manufacturers and proprietary Linux trees and their complete ignorance or lack of enthusiasm to contribute upstream. The presentation had information about how vendors were still using old obsolete Linux trees, which had several security flaws and the fixes were not being provided to users. The last keynote was from Kalyan Verma. Unlike the first keynote that lacked a single illustration, this one was full of award winning pictures, FOSS principles applied to other professions and life and also about the environment. How a cup of tea is playing its part in hurting the environment and the stress that we as humans and our requirements is putting on nature. Kalyan also spoke about his previous job as a security expert at Yahoo. He spoke about how cryptography makes no sense and there were obvious security flaws in most implementations. I disagree with Kalyan on some of the things he said about cryptography (like it makes no sense). I think what Kalyan was alluding to, but failed to say was that, security is only as good as the weakest link (a fact known to almost all programmers by now).

Kalyan mentioned that putting up his photographs under creative commons has gone a long way in helping his career. Since the pictures were free to download, they were shared under creative commons, which lead to newer opportunities and work. He went on to say, Pictures are a remarkable form of art. The more you look at them, the more you admire them, which is why sharing his pictures brought in more work and money.

Do check his photographs, they are really cool! James has a good coverage of his keynote as well.

The FOSS.IN team put out a video documentary covering their aspiration for their event and what was achieved. I'd say with FOSS.IN 2008, we've headed in the right direction, probably lost a few people along the way, but we are headed in the right direction. A technical event such as FOSS.IN should focus on contributions and try to encourage and build the mind share for it. Such a direction requires time and patience and also a lot of will power from both attendees and the organizers. We had a drastic change in sponsors this year, but we had them nevertheless, without whom such a large scale operation is hard to carry out.

The food, lunch and snacks were excellent, again James covered it well with photographs and other photographs marked foss.in on flickr. Here are some more memories from FOSS.IN 2008



Photo by Sony Phil


Photo by James Morris


From mdemon


From Sony Phil, photograph from the libcgroup workout

Lagrange's interpretation in python

I've been reading up on Fast Fourier Transform (FFT) from several books on algorithms that I have, TCLR, Tamassia, Sahni, Numerical Recipes, a big set of DSP books. Several of these books focus on interpolation before touching upon the subject of FFT. My favourite book so far for numerical algorithms is R.W. Hamming's Numerical Methods for Scientists and Engineers, Second Edition, Dover publication. Chapter 14, touches upon this topic. I love his explanation and illustration of interpolation versus extrapolation. Thinking along that subject, I decided to do some implementation of my own for interpolation. Sahni (Computer algorithms in C++) has an understandable implementation of the algorithm. The biggest drawback was implementing my own polynomial class. This is where, I think Python scores. I found that SciPy implements a polynomial class.

Here is the code for interpolation

def lagrange(x):
tmp = scipy.poly1d([0])
result=scipy.poly1d([0])

for i in x.keys():
 numerator=scipy.poly1d([1])
 denom = 1.0
 for j in x.keys():
  if (i != j):
   tmp = scipy.poly1d([1,-j])
   numerator = numerator * tmp
   denom = denom * (i - j)
 tmp = (numerator/denom) * x.get(i)
 result = result + tmp

return result

input = {0:5, 1:10, 2:21}
print lagrange(input)

NOTE: Blogger keeps messing up my indentation, I am yet to figure out why.

Sahni's input for the example is {0:1, 1:10, 2:21} and I was surprised to see my program return a different output. Fixing the input, showed the correct results. That reminds me, somebody please ask Sahni to start maintaining useful errata for his books. I searched on the web and found nothing useful.

Running the same algorithm on y = log(x) and input = {1:0, 2:0.3010, 3:0.4771, 4:0.6021}, gave me 00.0123 x^3 - 0.1362 x^2 + 0.6236 x - 0.4997, which corresponds to the cubical approximation of log x (R W Hamming, page 233).

FOSS.IN 2008 Report (Part I)

FOSS.IN was an event I usually attended, last year I co-presented and this year presented and held a workshop at. I've been meaning to display promotional content on my blog

But... I could not :(

Anyway, the story is not over, even though foss.in for 2008 is. The promos show clearly what the organizers had in mind. I must admit that the organizers make me nervous with the schedule, with selected talks being announced about three weeks before the final event, when I was on vacation. The schedule and slides can be found here. I presented on control groups and organized a workout for libcgroup. Both were well received with significant queries at the end of the talk and good workout participation. We got several patches posted during the workout and after. The workout plan and updates are here.

One of the things we did well this year, was the kernel hacker day at foss.in and followed it up with a successful workout. We had a good number of people come and talk to us about the kernel, their intention to contribute and the issues they face. We admittedly had a plan 9 fan, apart from Christoph Hellwig. There were lightening talks and I spoke about my ideas on building a threaded RB tree for Linux.

Kernel Hacker Gathering (Photo by James Morris as seen on flickr)

There are some fun photos, that several people took. Kushal from Fedora took some very nice ones. He was kind enough to photograph all women and leave me out. Needless to say Kushal, you owe me a T-shirt and I want it now! James Morris, did a good job of taking photographs as well.

(Photo by James Morris as seen on flickr)

(Photo by James Morris as seen on flickr)

One thing that did catch my attention was my T-Shirt with my name on it. I love the T-Shirt and hope it stops choking me, when I wear it, someday :)

Speaker T-Shirts (Thanks, well done guys!!)

I was caught working, I could show the code if needed!

You can find James' photo set here.

Lets step back, the event began with a video from team FOSS.IN

Atul has always been a good speaker, he began by explaining the motivation for the change this year and ate an Apple on the stage, claiming that it was only low hanging fruit in the conference and he ate it :) Unfortunately for Atul, we provided other low hanging fruits to developers and allowed people to contribute, even if the contribution was trivial. In the longer run, as foss.in proceeds year and year, I think we'll find the low hanging fruits disappear as the developers mature and our contributions mature.

I'll update on the keynotes, the other speakers and more interesting stuff in part II, stay tuned.