Ravi Mohan's Blog

Thursday, March 17, 2005

Levelling up in Math land

(Edited on Feb 4 2011), This entry is correct but is now obsolete.I rewrote this with more detail here. Please use that instead.

Concrete Mathematics is a fine book. But in the very first there is a bit of handwaving that goes on to eventually get seemingly magical and the novice who is using the book for self study (iow, someone like me ) can get lost very easily .

A good example is the "solving a rcurrence by the repertoire method " explanation on pages 12 - 15 ). A margin note by a student (an excellent idea to include these) warns us "Beware . authors expect us to figure out the idea of the repertoire method by seat-of-the-pant examples instead of giving us a top down presentation " .

Unfortunately that doesn't help a reader to figure out what is going on and how to use the "repertoire method " to solve a recurrence . I've been banging my head against this for a few hours and i think i found out how the repertoire method works . here it is .

I will use the same recurrence the authors use .

Recurrence R =

f(1) = alpha
f(2n) = 2 * f(n) + beta for all n greater than or equal to 1
f(2n + 1 ) = 2 * f(n) + gamma for all n greater than or equal to 1
to solve a recurrence using the repertoire method ,

step 1
make sure that the recurence is expressible as a sum of parameters multplied by functions of n

the above recurrence can be transforemd to f(n) = A(n)*alpha + B(n)*beta +C(n)* gamma (this is done on page 13 of the book so i don't repeat it here)

where A, B and C are functions on n and alpha beta and gamma are constants

step 2
p times , where p is the number of parameters (in the above case, alpha, beta and gamma so p = 3 ) *assume* that f(n) = a simple function of n and solve using the original recurrence to get an equation . eg: in the above recurrence there are three parameters , alpha , beta and gamma

so say
f(n) = 2^m, --> Eq(1) (EDITED on Feb 4, 2011 - This is actually proved by induction in the book so this guess for the value of f(n) , but this guess does work in providing the value of A(n) better than proving it by induction)
f(n) = 1 -->Eq(2) and
f(n) = n -->Eq(3) be your assumed functions .

solving R with Eq(1) gives A(n)= 2^m --> Eq(4)
Solving R with Eq(2) gives A(n) - B(n) -C(n) = 1 -->Eq(5)
and solving R with Eq(3) gives A(n) + C(n) = n --> Eq(6)

step 3
solving these 3 equations (eqs 4,5 and 6) gives us the values of the coefficients .

A(n) = 2^m
B(n) = 2^m -1 - l (the last is the letter "ell" )
and C(n) = l (the letter ell)
thus the closed form of the recurrence is

A(n) alpha + B(n) beta + C(n) gamma = 2^m * alpha + (2^m - 1 -l) * beta + l*gamma

now the question is how can we be sure that we guess the "right" functions in step 2 ? how do we know that f(n) = 1 is a "good " guess ?

the answer is that if you guess "wrong" you won't be able to solve for that equation and will end up with an impossible equality .

and that is how the repertoire method works!

happy repertoiring

Monday, March 07, 2005

None So Blind... The Agile India Conference Experience Report Part 2

Thanks to problems setting up the laptop I missed Brett's presentation. I listened to Mridul's talk on "Kernel Programming + Agile" and then it was my turn . We grabbed some lunch and then went to see if we could attend some seminars . Unfortunately all of the presentations in the afternoon were boring as hell . Most were about "combining waterfall and agile" Apparently there was a talk earlier in the morning about a "wagile" methodology . If you, the reader, just fell off your chair or threw up , you can imagine my reaction.

I think God is having His revenge on me for generally being disrespectful and specifically for using a Dilbert Cartoon as a presentation aide. when i looked at all those PHB types drone on and on about "waterfall and agile are complementary " , i felt i was inside a Dilbert strip . I think a lot of clueless managers in Bangalore have latched on to the "latest buzzword" and are busy "optimizing" (bwaaa ha ha !! this is a private joke . i actually met a (totally dilbertian) manager who said "my main skill is optimizing" if you mention this to Abey or me, we'll fall around in hysterics ) and "combining" it with whatever outmoded nonsense they know about "managing software teams" .

It is very frustrating to see how much traction this stupid idea is getting in Bangalore amongst people who don't want to change how they or their companies function but want to be "agile" so they can fool their clients into giving them more money.

I have said so before and i will say it again .

The primary facilitating factor for "going agile" is a culture that respects no hierarchy but that of competence and maintains an atmosphere of total openess and trust.

now how many companies in Bangalore work like this ? 3 ? 5 ? you get the idea .

In the evening the organizers asked me to be on a panel on "distributed agile " . There was this person on the panel (who shall remain nameless) who claimed that his "whole life is agile" (!!! ) and then went on to proclaim a lot of "waterfall " ideas (eg:" 'novices ' should have their yahoo messengers monitored by a 'senior' developer to make sure they don't say anything "dangerous" to a client" ).I have never heard such nonsense in my life . I really lost my cool and did what i could to rip his arguments apart.

The audience loved it :-D .

An artist sketching the panel drew me in a furious, scowling figure. If i can get a copy of the drawing from Manoj Bharadwaj i will certainly put it up here .

Because one of my friends was leaving Bangalore , i missed the second day of the conference .

too bad, because i was looking forward to hear Fred George, Dakshinamurthy Karra ,Simon Harris(author of Simian), Henry Jacob and Luke Barret speak .The last two seem to be focussed on Interaction Design in an agile fashion. Alas it was not to be .

All in all it is wonderful that such conferences are happening in India . If the Agile India Society can just keep going we may see many more such events .On the other hand it may just wither and die.

we'll see .

Sunday, March 06, 2005

Slide, Slide on the wall... The Agile India Conference Experience Report Part 1

I attended (and spoke at) the Agile India Conference. My speech about applying XP to a large AI classifier system I am working on was well received . I used slides only to represent visualisation of complex data (and one for a dilbert cartoon).

I think most people use slides because
  1. they need to structure their thoughts as they create their speech,
  2. they can "lean on" the slides,use them as a psychological crutch while on stage,to take away some of the stress associated with speaking
  3. that is the only way they know how to make a presentation. That is how they learned to do it

Though i was a fairly good speaker and debater in college ,soon after i got into the software "industry" (note the quotes) i fell into the habit of creating and using slides for presentations. Recently i read this , this and this .

I also noticed that the very best speakers , even in the software field, (example Martin Fowler ) do not use slides .

ok so here was a chance to face an audience without any shields again after many years . The surprising thing was how powerful the hold of PowerPoint was. Though,years ago, i had spoken to large audiences before, without slides,or even notes, now it felt very strange to do so without PowerPoint guarding my back !! this was scary !

anyway , an intial awkwardness aside, the speech went off fine . The best compliment was given by a student volunteer (the conference was held at the PESIT Engineering College) who declared that he was able to follow the talk easily, though it was about a highly technical topic.

Vivek Singh , whom i respect tremendously, even while disagreeing with him about most things , was there and he didn't throw his shoes at me . .

So i guess it all turned out fine .Thanks to the talk, I met a lot of interesting people , including a person who writes browsers for mobile phones .We had a very interesting conversation.

And i will never use PowerPoint again . What i need is something that would allow me to outline the structure of a speech as i am speaking, annotate it with audience questions(as recorded audio ? ), connecting links etc .A cross between an outliner,a multi media blogging tool and a brain map .. hmmm time to fire up squeak.

More about the conference in the next entry .