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

## 4 comments:

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.

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 !)

is the book concrete maths available in the Indian market?

yes.

Post a Comment