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

3 comments:

Anonymous said...

Hi Ravi...Have you dropped this thread? Would like to know where you have reached w.r.t learning mathematics.
Iam sick and tired of writing code for UI-->DB-->UI...would like to exercise some grey cells.
Are you aware of any Indian software companies that fiddle with high end mathematics? I have a M.S in mathematics from BITs....don't want to waste my whole life writing atrocious enterprise software, as iam doing now.

Ravi said...

Pushottam,
I'll answer your questions in sequence.

"Would like to know where you have reached w.r.t learning mathematics"

My study of mathematics was motivated by my need to understand some complex AI algorithms.

As such so far i have focussed on
1.Linear Algebra
2.Calculus (+ some Real Analysis)
3.Probability and
4.Game Theory
I'll soon need to bone up on Statistics because i need to write some code that measures statsitical significance.

"Are you aware of any Indian software companies that fiddle with high end mathematics? "

Hmm i don't know about Maths companies per se but companies like Google India or Yahoo research (or any company with Research attached to its name) shuld snap you up if your programming skills match your math skills.

I am impressed with the bITS MS in Maths ! I barely squeaked through my B.Tech. I was almost nver in class and was out chasing girls or attending arts fests! In retrospect if i had been a "good boy" and studied Industrial Engineering better , i might be slaving in L and T, or maintaining mainframes,like many of my batch mates.


The one piece of advice i have is that you aso understand an area (like text search or dta mining) thet relies heavily on math skills and apply your math skills to develop code in that area .

I wish you the best (and buy me a beer when you get that google job !)

Anonymous said...

is the book concrete maths available in the Indian market?