(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 ,
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
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
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)
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!
Ravi Mohan's Blog
Monday, March 07, 2005
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
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
- they need to structure their thoughts as they create their speech,
- 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
- that is the only way they know how to make a presentation. That is how they learned to do it