Context: Everyone and his dog is hyperventilating on the internet about the death of Steve Jobs.
Here is my opinion (which like most opinions isn't worth very much, but hey this is my blog).
All men are mortal.
Steve Jobs was a man. (A great man, but still, a man.)
[Modus Ponens] Steve Jobs was mortal too.
Now he has died. The world endures. Life goes on.
Your (and my) time to depart will soon be here. The world will still endure. And life will still go on.
I read somewhere that the one regret most people have at the moment of death is about how they should have done X or Y instead of A or B.
Get back to work. Do X or Y instead of A or B. Die happy, when your time comes.
To the degree one admires Jobs, emulating his virtues in your life is a more fitting tribute than another silly comment about how he was as influential as Plato and Aristotle (an idiot actually said this on HN).
Update: on Stallman's comment on Steve Jobs' death. People have different ideas on whether a person's achievements were good or bad. This affects their judgement of whether a person's death was "good for the world" or not.
Stallman thinks that the end of Steve's influence on computing (note: he clearly distinguished it from Steve's death itself) is a good thing. And said as much.
I don't agree.
I think, for all his faults (and like you, me and every human who ever lived, he had some) Steve's influence was beneficial (overall) and I wish he'd lived longer.
But I also think it is ok for people (including Stallman) to express their opinions, even when I find them not in agreement with my own.
I look forward to the day when everyone (including me) will shut up about how other people should think exactly like everyone else.(or else we'll all get all self righteous and puffed up and hyperventilative).
And now I'll go back to coding. (Thank You for reading this far.You really should be doing something useful instead!)
Saturday, October 8, 2011
Monday, August 15, 2011
On Owning a Kindle
I was gifted a Kindle a month or so ago. I like it for what it does.
Should you buy one? If you are a book lover, one of those people who always have a book on hand, or reach for one when you have an hour to spare, you definitely should. If you read mostly technical or math books (which require a lot of flipping back and forth and good rendering of code or equations)or research papers, you won't get as much benefit as you ought to.
I am well satisfied with the Kindle for allowing me to lug around about 300 books (I still have almost 3 GB left) so I can read on the bus, while waiting for someone, etc. I would have loved it if I could read math books and papers (pdf rendering on the (small) kindle is terrible) and also scribble notes (the kindle "make notes" functionality is awkward and unusable) but e-ink based readers are still in their early days. For what it does (enable you to carry around a few hundred fiction books it is awesome. For example, I have all the 20 Aubrey Maturin books and the dozen or so Jim Butcher books in a 6 inch device. (E-Paper blows away IPad's screen for reading.)
If I'd received the Kindle before the release of George Martin's utterly terrible "A Dance With Dragons" (I should write a blog entry one of these days on how terrible it is - suffice to say that the man has lost his touch) I could have spent 11$ on a kindle version instead of 54 $ (18 for the book, the rest for postage to India). The Kindle shines for fiction and light non fiction books. And you can avoid paying for the kindle editions by downloading "pirated" versions if you know where to look. I suspect it would work well for magazine subscriptions too ( at least for those in which the written word is more important than glossy pictures).
Somewhat tangentially, someone should write a piece of software that works like LaTex for math but generates flowable text. Tex is (print) page oriented.If you could just take a LaTex file and generate a kindle readable document out of it,I suspect a lot of math/tech papers would find their way on to e-readers very fast.
After having used the kindle for a while I am not surprised that Amazon sells more e-books now than paper books. I suspect the Kindle is a very potent weapon in Amazon's arsenal, that its competitors underestimate. If they make it work in the Indian context, (Amazon plans to launch in India in 2012 - I have no idea how much of a role they plan for the Kindle here), their competitors will get swatted aside like so many flies. (Hmmm I should write a post on how I see the Amazon-Flipkart battle shaping up in India. Interesting times we live in).
Meanwhile, if you are a reader and can afford to buy a Kindle, you should. It (or something like it) is the future of reading.
Monday, June 27, 2011
Two Roads Diverge - Machine Learning or IOS Dev?
Now that my latest project (for those interested in such things - 30 k lines of Haskell, 200 k lines of (mostly legacy) C/C++ code, a few thousand lines of Lua, signal processing, some NLP ish things) is "done done"[1] I have to choose [2] a new project.
Choosing a new project is always an exciting time, but also a mildly stressful one. For every choice made, a half dozen equally worthy alternatives have to be rejected. And I do a lot of agonizing over what is the 'right' project to take up.
One way to maintain a sense of continuity among projects is to examine what could have been done better on the finished project and see if you can build a project around fixing those deficiencies.
Working on the last project exposed some flaws in my dev chops - I know nothing about Network Programming and this caused me to take longer than usual to fix a few nasty bugs that cropped up. So I'd like to take a couple of months off and work through Stevens's books and close this gap and then build some customized network monitoring tools which I could have used when my hair was on fire. Our visualization and rendering subsystem used an Open Source renderer that fell down on large datasets. NLP algorithms in Haskell had to be painfully built one by one. The Computer Vision library we used (Open CV) is a friggin mess that needs serious surgery. And so on. Doing all that would multiply the existing codebase's power by a factor of 10. And also make good building blocks for new projects.
And many ML projects have the strange property that completing them successfully opens up even more ambitious projects. The folks who sponsored the last project want me to do more stuff for them.
Another way to choose a new project to work on is to find great people you'd like to work with and build a project around what they are doing or are interested in. My stubborn refusal to move to the USA somewhat limits my choice in this regard - Not many people or companies in Bangalore are doing anything interesting in Machine Learning. But otoh a few people have bounced really (really really) interesting IOS projects (and start up plans) to me. On the one hand, this means I have to go over to the Dark Side and sell my soul to the evil but competent folks at Apple and learn Objective C and overpay for a MacBook and the annually renewed right to put software I write on hardware I already paid for and so on. Being a storm trooper for Darth Steve is a proposition that requires some thought. But on the other hand, I would be working with ultra competent devs again (Working alone, or as the only dev on a team is the only negative - and it is a small one - in my 'lifestyle'. Fixing that would rock).
A third choice - I actually thought of sitting down and writing a book, just for a change of pace. I have a few ideas for some tech books I think are missing from thes shelves and every dev I pitched reacted with a variant of "I'd buy that RIGHT now - please please write it". What stops me is that people who have written successful tech books say that it is a pretty thankless task, and with some exceptions, financially unrewarding (though your "prestige" goes up- something I don't care a rat's ass about). If I had to choose between spending a thousand hours writing a book and a thousand hours writing code, it is somewhat hard to choose the former.
Hence the "two roads diverge" tone that permeates my thoughts. I could dive deeper into Machine Learning(and allied areas) or go do mobile app stuff. Choosing promises to be interesting.
Two Roads Diverge and all that jazz[3]
But first, before I have to make a choice, clear the backlog of people to meet (I thank you all for your patience and suffering my erratic schedules), places to visit, things to do. (Metaphorically) lie on a beach somewhere with no computers in sight. Relax, refresh. Then decide.
[1] Most projects have an official "done " date and then a later "done done" date. In this case the project was 'done' some time ago and then a rookie dev wiped out the source control repo while simultaneously trying to alter the Haskell code (vs writing a minor script in Lua, which is what the situation called for), bringing the whole cluster down, causing the (non dev) owners of the project to send an SOS to me to get on a plane pronto and put out the fire.
Some fences have been built to avoid this kind of FUBAR situation from happening again so now I am "done done"
[2] One significant milestone in one's evolution as a developer is when you realize that you have more ideas than you can implement in your lifetime. You are even luckier when people pay you to implement them (vs being assigned to some Godawful Leasing System dev in some enterprise dev body shop say)
[3] - From Frost's poem, of course
Two roads diverged in a yellow wood,
And sorry I could not travel both
And be one traveler, long I stood
And looked down one as far as I could
To where it bent in the undergrowth.
...................................
I shall be telling this with a sigh
Somewhere ages and ages hence:
Two roads diverged in a wood, and I
I took the one less traveled by,
And that has made all the difference.
Choosing a new project is always an exciting time, but also a mildly stressful one. For every choice made, a half dozen equally worthy alternatives have to be rejected. And I do a lot of agonizing over what is the 'right' project to take up.
One way to maintain a sense of continuity among projects is to examine what could have been done better on the finished project and see if you can build a project around fixing those deficiencies.
Working on the last project exposed some flaws in my dev chops - I know nothing about Network Programming and this caused me to take longer than usual to fix a few nasty bugs that cropped up. So I'd like to take a couple of months off and work through Stevens's books and close this gap and then build some customized network monitoring tools which I could have used when my hair was on fire. Our visualization and rendering subsystem used an Open Source renderer that fell down on large datasets. NLP algorithms in Haskell had to be painfully built one by one. The Computer Vision library we used (Open CV) is a friggin mess that needs serious surgery. And so on. Doing all that would multiply the existing codebase's power by a factor of 10. And also make good building blocks for new projects.
And many ML projects have the strange property that completing them successfully opens up even more ambitious projects. The folks who sponsored the last project want me to do more stuff for them.
Another way to choose a new project to work on is to find great people you'd like to work with and build a project around what they are doing or are interested in. My stubborn refusal to move to the USA somewhat limits my choice in this regard - Not many people or companies in Bangalore are doing anything interesting in Machine Learning. But otoh a few people have bounced really (really really) interesting IOS projects (and start up plans) to me. On the one hand, this means I have to go over to the Dark Side and sell my soul to the evil but competent folks at Apple and learn Objective C and overpay for a MacBook and the annually renewed right to put software I write on hardware I already paid for and so on. Being a storm trooper for Darth Steve is a proposition that requires some thought. But on the other hand, I would be working with ultra competent devs again (Working alone, or as the only dev on a team is the only negative - and it is a small one - in my 'lifestyle'. Fixing that would rock).
A third choice - I actually thought of sitting down and writing a book, just for a change of pace. I have a few ideas for some tech books I think are missing from thes shelves and every dev I pitched reacted with a variant of "I'd buy that RIGHT now - please please write it". What stops me is that people who have written successful tech books say that it is a pretty thankless task, and with some exceptions, financially unrewarding (though your "prestige" goes up- something I don't care a rat's ass about). If I had to choose between spending a thousand hours writing a book and a thousand hours writing code, it is somewhat hard to choose the former.
Hence the "two roads diverge" tone that permeates my thoughts. I could dive deeper into Machine Learning(and allied areas) or go do mobile app stuff. Choosing promises to be interesting.
Two Roads Diverge and all that jazz[3]
But first, before I have to make a choice, clear the backlog of people to meet (I thank you all for your patience and suffering my erratic schedules), places to visit, things to do. (Metaphorically) lie on a beach somewhere with no computers in sight. Relax, refresh. Then decide.
[1] Most projects have an official "done " date and then a later "done done" date. In this case the project was 'done' some time ago and then a rookie dev wiped out the source control repo while simultaneously trying to alter the Haskell code (vs writing a minor script in Lua, which is what the situation called for), bringing the whole cluster down, causing the (non dev) owners of the project to send an SOS to me to get on a plane pronto and put out the fire.
Some fences have been built to avoid this kind of FUBAR situation from happening again so now I am "done done"
[2] One significant milestone in one's evolution as a developer is when you realize that you have more ideas than you can implement in your lifetime. You are even luckier when people pay you to implement them (vs being assigned to some Godawful Leasing System dev in some enterprise dev body shop say)
[3] - From Frost's poem, of course
Two roads diverged in a yellow wood,
And sorry I could not travel both
And be one traveler, long I stood
And looked down one as far as I could
To where it bent in the undergrowth.
...................................
I shall be telling this with a sigh
Somewhere ages and ages hence:
Two roads diverged in a wood, and I
I took the one less traveled by,
And that has made all the difference.
Sunday, May 29, 2011
"Civil-Society Hacker" barcamp at Google Gurgaon
Without extra comment, an email I received. If you are interested in this kind of thing and/or live near Gurgaon, maybe you should take a look.
From:
"Laina Emmanuel" < lemmanuel@accountabilityindia.org >
Dear Ravi,
I came across your blog while looking for hackers in India. I am looking for civil-society hackers who would like to use their programming skills to develop innovative solutions for governance. To facilitate a conversation between programmers and policy-makers, I am organizing (if it can be called organizing) a bar-camp at the Google Campus in Gurgaon, on "Technology, Transparency and Accountability" on the 5th of June.
This bar-camp is being held by Accountability Initiative. Founded in 2008, Accountability Initiative is a research initiative that aims to improve the quality of public services in India by promoting informed and accountable governance. To this end, one of AI's key efforts is to develop innovative models for tracking government led social sector programs in India. The Centre for Policy Research, an independent and non-partisan research institute and think-tank, is the institutional anchor for this initiative.
We have a wide variety of participants for the bar-camp ranging from policy-makers to technology-enthusiasts. We would be honored if you could also join us at this bar-camp and help show how hackers can contribute to governance. Also, we would really appreciate it if you could forward this invitation to others who would be interested.
Thanks and regards
Laina Emmanuel
I have no affiliation with any of the organizations mentioned in the email. Write to Laina for details.
From:
"Laina Emmanuel" < lemmanuel@accountabilityindia.org >
Dear Ravi,
I came across your blog while looking for hackers in India. I am looking for civil-society hackers who would like to use their programming skills to develop innovative solutions for governance. To facilitate a conversation between programmers and policy-makers, I am organizing (if it can be called organizing) a bar-camp at the Google Campus in Gurgaon, on "Technology, Transparency and Accountability" on the 5th of June.
This bar-camp is being held by Accountability Initiative. Founded in 2008, Accountability Initiative is a research initiative that aims to improve the quality of public services in India by promoting informed and accountable governance. To this end, one of AI's key efforts is to develop innovative models for tracking government led social sector programs in India. The Centre for Policy Research, an independent and non-partisan research institute and think-tank, is the institutional anchor for this initiative.
We have a wide variety of participants for the bar-camp ranging from policy-makers to technology-enthusiasts. We would be honored if you could also join us at this bar-camp and help show how hackers can contribute to governance. Also, we would really appreciate it if you could forward this invitation to others who would be interested.
Thanks and regards
Laina Emmanuel
I have no affiliation with any of the organizations mentioned in the email. Write to Laina for details.
Friday, April 8, 2011
Why startups in India find it hard to hire devs
Mayank Sharma wrote an interesting blog post about hiring difficulties for startups in India. He says the reasons are
(1) The very good devs can work for multinationals (Google,Microsoft etc) and local startups can't match the compensation.
(2) Indian services companies have lock in contracts
(3) No real history of non founders making lots of money from a startup
(4) Those who do want to work for startups have "unreasonable expectations" (quotes mine, not his)
Manoj Govindan (who works for (startup) Perfios - due disclosure - I reccomended him to Perfios - guilty as charged! :-) ) responded with four reasons why these startups don't hold any allure for good devs
(1) very few Indian startups offer significant equity to early hires.
(2) Many Indian startups give employees little say in strategic decision making. In the end, you are still a "coding body".
(3) Signal/Noise ratio - too many "social this" "cloud that" clone startups out there than innovative ones. Noise attracts noise.
(4) "Very good guys" like to make own technical decisions. Here they find them already made and locked in before they join. Often tech stacks are in place even before people actually decide what to do.
I have some sympathy for both view points. Is the question such a complicated one though?
There is a simpler explanation. All the points above can be subsumed under "Whenever there is a demand and supply gap, and some kind of free market mediating the two, prices rise". That is it.
Good devs, those with the combination of tech chops, communication skills, attitude and *ambition* (iow the exact type you want for your startup) are a scarce resource generally and particularly so in today's market. Demand is very high (this fluctuates) and supply is very low (this is constant). In such a scenario, the price varies from very high to high. Right now it is very high. And that is it.
You just can't buy gold for peanuts (speaking metaphorically. In reality you can trade a few truckloads for some gold). I can't. You can't. It is a value neutral statement - just the way the market works. You can sometimes marginally route around the Iron Law of supply and demand - Zoho trains people who wouldn't be considered for normal dev jobs for e.g - in effect, creating their own supply - but you can't escape it.
Even then, the argument goes, the "price" for good devs isn't necessarily all about money. True enough.
Look at how Silicon Valley's startups (or even more narrowly, YC funded companies) hire good devs - If you can't match (or exceed) market price in terms of compensation you need to make it up with (a) significant equity and/or (b) advanced tech and/or (c) a compelling business model with some traction and/or (d) a "change the world" product (think SpaceX) or (e) credible, proven founders. This is true *everywhere*, not just in the valley, though details and leeway differ. If you are a company trying to hire the very best developers, you have to pay the price somehow.
The typical Indian "lean startup" fails on all counts - it is often doing some whacky buzzword heavy, content lite, mobile/social mini app, works on PHP and MySQL, has no money (and so offers bare minimum salaries), is often run by clueless MBA/undistinguished engineer types and will give a prospective employee 1% equity in a doomed product for an endless 18 hour working day.
Why the hell would anyone half way technically good want to work with such outfits?
Devs are sometimes economically stupid but they aren't *that* stupid.
If they want to do interesting tech stuff they can go work for Google (Mountain View, not Bangalore!), start their own "great tech" companies, work on Open Source projects, work from home for US based startups doing interesting things or wait for Indian startups with cutting edge tech to proliferate, meanwhile drawing a steady salary and honing their skills.
If you must stay in Bangalore, but want great tech and a small company, go work for Gluster. All the tech and Open Source you want. Or apply to Tachyon. Or Notion Ink. There are a *lot* of companies attempting technically interesting things in Bangalore these days. And there is space for many many more, if you have founder dreams.
If you want to do services web dev, and work with small teams of bright people in a great office atmosphere, they should go work for someone like C42. Good company I vouch for.
If you just want to get out of that crappy enterprise services bodyshop, but don't want to get stressed about whether your children will starve, *and* want to do something "like a startup, but stable",go work for (a) someone with traction and funding, but aren't quite a startup any more (say SlideShare or Inmobi or Flipkart) (b) work with one of the many offshore centres of product companies, who have plenty of money. (say Intuit,or Zynga).
If you choose to be an employee (and it is an honourable choice), always make sure you are getting what you are worth - be that in terms of money, equity or technical challenge or whatever your individual preference is. This is just plain common sense.
If you want to be entrepreneurial and don't mind the stress, be a (co)founder, not an employee. That way you can still work on the latest social/mobile ripoff idea in PHP (or the blue sky idea in your own custom language!) and scrounge around for money, but you'll be in control of your destiny and won't have to factor in crazy bosses. ;-)
Nutshell : The law of demand and supply explains all phenomena in a free market. If you are any good at programming, you have more options now than you ever did. If you want to hire such people, create a compelling value proposition. If you aren't getting enough applications from qualified devs your "offer" isn't good enough.
The End.
EDIT: someone asked about good startups in Pune. The only Pune based startup I know of is Infinitely Beta (who have no problems recruiting afaik). But I am no expert on Indian startups.Do your research!
EDIT 2: I dashed this off while waiting for a build to complete. Apologies in advance for any typos/flaws.
(1) The very good devs can work for multinationals (Google,Microsoft etc) and local startups can't match the compensation.
(2) Indian services companies have lock in contracts
(3) No real history of non founders making lots of money from a startup
(4) Those who do want to work for startups have "unreasonable expectations" (quotes mine, not his)
Manoj Govindan (who works for (startup) Perfios - due disclosure - I reccomended him to Perfios - guilty as charged! :-) ) responded with four reasons why these startups don't hold any allure for good devs
(1) very few Indian startups offer significant equity to early hires.
(2) Many Indian startups give employees little say in strategic decision making. In the end, you are still a "coding body".
(3) Signal/Noise ratio - too many "social this" "cloud that" clone startups out there than innovative ones. Noise attracts noise.
(4) "Very good guys" like to make own technical decisions. Here they find them already made and locked in before they join. Often tech stacks are in place even before people actually decide what to do.
I have some sympathy for both view points. Is the question such a complicated one though?
There is a simpler explanation. All the points above can be subsumed under "Whenever there is a demand and supply gap, and some kind of free market mediating the two, prices rise". That is it.
Good devs, those with the combination of tech chops, communication skills, attitude and *ambition* (iow the exact type you want for your startup) are a scarce resource generally and particularly so in today's market. Demand is very high (this fluctuates) and supply is very low (this is constant). In such a scenario, the price varies from very high to high. Right now it is very high. And that is it.
You just can't buy gold for peanuts (speaking metaphorically. In reality you can trade a few truckloads for some gold). I can't. You can't. It is a value neutral statement - just the way the market works. You can sometimes marginally route around the Iron Law of supply and demand - Zoho trains people who wouldn't be considered for normal dev jobs for e.g - in effect, creating their own supply - but you can't escape it.
Even then, the argument goes, the "price" for good devs isn't necessarily all about money. True enough.
Look at how Silicon Valley's startups (or even more narrowly, YC funded companies) hire good devs - If you can't match (or exceed) market price in terms of compensation you need to make it up with (a) significant equity and/or (b) advanced tech and/or (c) a compelling business model with some traction and/or (d) a "change the world" product (think SpaceX) or (e) credible, proven founders. This is true *everywhere*, not just in the valley, though details and leeway differ. If you are a company trying to hire the very best developers, you have to pay the price somehow.
The typical Indian "lean startup" fails on all counts - it is often doing some whacky buzzword heavy, content lite, mobile/social mini app, works on PHP and MySQL, has no money (and so offers bare minimum salaries), is often run by clueless MBA/undistinguished engineer types and will give a prospective employee 1% equity in a doomed product for an endless 18 hour working day.
Why the hell would anyone half way technically good want to work with such outfits?
Devs are sometimes economically stupid but they aren't *that* stupid.
If they want to do interesting tech stuff they can go work for Google (Mountain View, not Bangalore!), start their own "great tech" companies, work on Open Source projects, work from home for US based startups doing interesting things or wait for Indian startups with cutting edge tech to proliferate, meanwhile drawing a steady salary and honing their skills.
If you must stay in Bangalore, but want great tech and a small company, go work for Gluster. All the tech and Open Source you want. Or apply to Tachyon. Or Notion Ink. There are a *lot* of companies attempting technically interesting things in Bangalore these days. And there is space for many many more, if you have founder dreams.
If you want to do services web dev, and work with small teams of bright people in a great office atmosphere, they should go work for someone like C42. Good company I vouch for.
If you just want to get out of that crappy enterprise services bodyshop, but don't want to get stressed about whether your children will starve, *and* want to do something "like a startup, but stable",go work for (a) someone with traction and funding, but aren't quite a startup any more (say SlideShare or Inmobi or Flipkart) (b) work with one of the many offshore centres of product companies, who have plenty of money. (say Intuit,or Zynga).
If you choose to be an employee (and it is an honourable choice), always make sure you are getting what you are worth - be that in terms of money, equity or technical challenge or whatever your individual preference is. This is just plain common sense.
If you want to be entrepreneurial and don't mind the stress, be a (co)founder, not an employee. That way you can still work on the latest social/mobile ripoff idea in PHP (or the blue sky idea in your own custom language!) and scrounge around for money, but you'll be in control of your destiny and won't have to factor in crazy bosses. ;-)
Nutshell : The law of demand and supply explains all phenomena in a free market. If you are any good at programming, you have more options now than you ever did. If you want to hire such people, create a compelling value proposition. If you aren't getting enough applications from qualified devs your "offer" isn't good enough.
The End.
EDIT: someone asked about good startups in Pune. The only Pune based startup I know of is Infinitely Beta (who have no problems recruiting afaik). But I am no expert on Indian startups.Do your research!
EDIT 2: I dashed this off while waiting for a build to complete. Apologies in advance for any typos/flaws.
Friday, February 4, 2011
The repertoire method in "Concrete Mathematics"
Concrete Mathematics by Knuth et al is a great book but there are a couple of places where people learning by themselves can stumble, fall and get lost.
When I originally worked through the book I couldn't make head or tail of the "repertoire method" of solving recurrences. Eventually I did figure it out and sometime later I wrote up what I understood and posted it on my (then) blog. It seems that a lot of people search for "Concrete Mathematics Repertoire method" on Google and it is my second most popular blog post (The most popular post is this one, fwiw)
So I re-read the repertoire method post today and while it is correct, I can explain it better today so here goes.
(What follows may not make sense to you if you are not working through CM (be warned!). Also be warned that I have no formal training in mathematics, computer science or programming and am entirely self taught. So people with such training can probably explain things better. The following reflects only *my* understanding. That said, onwards!)
By the time you hit the repertoire method section in Chapter 1 of Concrete Mathematics, you have been taught a simple method to find closed forms of recurrences. The essential algorithm is
(a) make a table of the recurrence values R(n) for small values of n.
(b) Eyeball the table to see if you can spot a pattern,
(c) write down the pattern.
(d) Prove (or disprove) the candidate closed form's correctness by Mathematical Induction over (a subset of) the natural numbers.
You used this method, for example to solve the Josephus problem, so you know where to stand (in the circle of your idiot friends trying to commit mass suicide) so that you end up being the survivor), surrender to the Romans and become a historian for the ages).
The repertoire method makes its (first) appearance in the generalization of the Josephus recurrence. The constants 1 and -1 are replaced by alpha beta and gamma to give the more general recurrence
f(1) = alpha
f(2n) = 2*f(n) + beta
f(2n + 1) = 2*f(n) + gamma~~~~~~~~~~~~~~~~~~~~~~~[1]
Your job is to find f(n) such that this recurrence is true for any values of alpha, beta, and gamma.
So how do you do this? You use the only technique you know (at this point in the book) of making a table for small values of n and eyeballing it to spot a pattern (I am too lazy to reproduce the table here, go buy the book!). You don't spot a pattern for the f(n) but you do notice that all values of f(n) follow a pattern of
f(n) = A(n)*alpha + B(n)*beta + C(n)*gamma~~~~~~~~~~~~~~[2]
This is a kind of template of what the final closed form will look like, depending of course on the values of A(n), B(n) etc
In other words if we can find functions A(n), B(n) and C(n) such that when given n they generate the right coefficients as in Table 1.12, then we have a closed form for f(n).
Something very important happened here. You broke down a problem into smaller subproblems.
You still don't know the value of f(n) but now you know that if you can find the values of the functions A(n), B(n), and C(n) you have solved f(n).
Now you can find these values with your trusted "spot a pattern and verify with induction" (the only tool you have at this point) OR you can use the (unexplained!) repertoire method.
The first bit of confusion arises because the authors do both. They guess values of all the three functions in n, A(n), B(n) and C(n) from the initial table, say (correctly) that proving that these values by induction is long and tedious and then they go ahead and prove that the guessed value of A(n) is correct by induction! (to be fair they are solving for only A(n) and not all the unknowns simultaneously but though smaller this induction is still tedious. Try it. I did.)
Or, in more detail,
a value is guessed, (that A(n) = 2^m , m coming from rewriting n as 2^m + k as in the original Josephus problem - the book uses the letter l instead of k, I use k to distinguish easily from the number 1), beta and gamma are set to zero (remember the recurrence has to hold for *all* values of alpha, beta and gamma, including the selected 1,0,0) and then the recurrence [1] is rewritten (using [2]) as a recurrence in terms of A(n).
I'll repeat that so it is clear what is happening
Step 1: Guess a value for A(n), by eyeballing.We guess A(n) = 2^m
Step 2: Select alpha, beta and gamma so that the other two functions of n, B(n) and C(n), get eliminated from [2]. You can do this by selecting alpha = 1 and beta = gamma = zero.
Step 3: Rewrite the equation [2] (i.e the observed generalized form) in terms of the selected values of alpha, beta and gamma. You get f(n) = A(n).
Step 4: Use this equation (ie f(n) = A(n)) and your chosen values of alpha, beta and gamma to rewrite the original recurrence (ie equation [1]) to get
A(1) = 1 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~[3]
A(2n) = 2*A(n)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~[4]
A(2n + 1) = 2*A(N)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~[5]
Now the problem becomes to prove that your guess (i.e, A(n) = A(2^m + k) = 2^m) satisfies this new recurrence as expressed by [3] and [4] and [5].
The authors state "Sure enough it is true (by induction on m) that A(2^m + k) = 2^m "
The authors don't show the induction but you can work out this (tedious but not difficult) induction. Only basic algebraic manipulation is required)
Be aware that (a) the induction is on m, not n and (b) the predicate to be proven has the form P_m: (A(2^m +k) => [3] AND [4] AND [5]).
First, prove P_zero (as m starts from zero, though n starts from 1 - we need an induction on m, not n!). Then prove that P_m => P_m+1. (Weak Induction is sufficient).
So we prove (yay!!) that A(n) does = 2^m.
You could do the same for B(n) and C(n). Select values for alpha, beta and gamma to create recurrences in terms of B(n) only and then C(n) only, just as we did above for A(n), then use mathematical induction over m to prove your guesses correct.
In the book though, the authors switch to the repertoire method to find B(n) and C(n). This switch is the first confusing bit - A(n) is found using a guess + induction (the old method - eyeball, guess, use induction). But then they switch - and the repertoire method is used to find B(n) and C(n) and the initial guesses as to their values are unused!
Worsening the confusion is the fact that the repertoire method is not identified or explained explicitly at this point. As a student states in a margin note (great idea btw) "Beware: the authors are expecting you to figure out the idea of the repertoire method from seats of pants examples instead of giving a top down presentation"
The seat-of-pants example is actually enough if A(n),B(n) and C(n) are all worked out with the repertoire method.
So let us solve the whole thing with the repertoire method (no induction) and see how it works. Let us throw away the guesses about the values of A(n), B(n), and C(n). We'll assume we couldn't make any guesses for A(n), B(n) and C(n).
All we have is the original recurrence
f(1) = alpha
f(2n) = 2*f(n) + beta
f(2n + 1) = 2*f(n) + gamma~~~~~~~~~~~~~~~~~~~~~[1]
and our observation that f(n) always has the form
f(n) = A(n)*alpha + B(n)*beta + C(n)*gamma~~~~~~~~[2]
ok so we don't know (and we need to find out) the values of A(n), B(n) and C(n) .
The repertoire method (for this recurrence) works like this.
(1) Guess a value for f(n). (ie the guess is for the whole of [2] NOT a component A(n) as we did above!)
(2)See if you can find values for alpha, beta and gamma to validate this guess. Rewrite [1], the original recurrence in terms of your guess for f(n). See if you can find values for alpha, beta and gamma.
(3) Substitute these values (of alpha, beta and gamma), back into [2]. You'll get an equation in terms of the three unknowns A(n), B(n) and C(n).
(4)Repeat steps (1) - (3) till you have three independent equations.
(5)Solve for three linear equations in three unknowns.
Done.
Important: If you make a "wrong" guess you will end up with a useless equation like 0 = 0 or an equation that is not independent of the already derived equations and so on. If this happens, don't worry about it, try another guess till you do get three independent equations.
In detail.
I guess (the authors do too) that f(n) = 1.
Rationale for the guess: f(n) = constant is the simplest possible formulation of f(n) (just for fun you might want to try f(n) = 0)
Let us try substituting this in [1]
f(1) = alpha becomes 1 = alpha (since f(n) is 1 for any n).
similarly
f(2n) = 2*f(n) + beta becomes 1 = 2*1 + beta so beta = -1
f(2n + 1) = 2*f(n) + gamma becomes 1 = 2*1 + gamma so gamma = -1
so we have values for alpha,beta, gamma and f(n) and when we substitute back into [2] we get
A(n) - B(n) - C(n) = 1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~[6]
ok!!! we have the first equation.
Now if we could get just two more independent equations like this we would have three equations in three unknowns (and so solve by Linear Algebra).
The authors use f(n) = n as their second guess and get A(n) + C(n) = n as their second equation.
(This is a good guess too. After f(n) = k, f(n) = n is the next rung up the complexity ladder. But in this specific example we can do better - see below)
and since they already proved that A(n) = 2^m by the "guess and use induction" method they don't need a third equation. They have two equations in two unknowns and they solve to get the solution.
But we don't have any guesses as to the values of A(n), so we can't plug that in.
We guessed at f(n) = 1 and got the equation A(n) - B(n) - C(n) = 1 and we need two more independent equations. We could re use the authors' f(n) = n guess and also cheat a bit and reuse the (non generalized) Josephus recurrence solution that we already proved that to "guess" that f(n) = 2k + 1. Then alpha = 1, beta = -1 and gamma = 1, giving us the third equation A(n) - B(n) + C(n) = 2k + 1. Three equations three variables. Solve. This gives the right answer too.
But that feels like a cheat. What if we hadn't solved the Josephus recurrence before? How would we guess f(n) = 2k + 1? We could go with f(n) = n but we can do better.
Since n = 2^m + k, we guess (our second guess)
f(n) = 2^m
and f(n) = k. (our third guess)
(Rationale for these guesses. Since n is dependent on 2^m and k why not guess with the simpler variables rather than f(n) = n, like the example in the book does? In this case this decision pays off spectacularly, giving the solutions for A(n) and C(n) directly and B(n) trivially )
These give us the equations, (just like we worked out [4] above, try it!)
A(n) = 2^m~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~[7]
C(n) = k~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~[8]
and these two along with [6] give us B(n) = 2^m - k - 1.
Look ma! no induction !
So now we have the values for A(n), B(n) and C(n) and now we can say that
the solution to the recurrence
f(1) = alpha
f(2n) = 2*f(n) + beta
f(2n + 1) = 2*f(n) + gamma is (given n = 2^m + k as explained earlier in the book)
f(n) = (2^m)*alpha + (2^m - k - 1)*beta + k*gamma.
Double checking,When alpha = 1, beta = -1 and gamma = 1 we get
the solution to
f(1) = 1
f(2n) = 2*f(1) - 1
f(2n + 1) = 2*f(n) + 1 (note: this is the original Josephus Recurrence)
is (2^m)*1 + (2^m - k - 1)*(-1) + k*(1), which resolves to
2k+1 which agrees with [1.9] (in the book).
Hopefully now what the authors say about the recurrence method makes more sense, though the sentence structure at this point in the book is confusing Let us take it apart - my comments in italics.
"First we find settings for parameters for which we know the solution" (the parameters here are alpha beta and gamma, the "solution"s are the various guessed values of f(n) NOT A(n),B(n), C(n). We make guesses for A(n),B(n) etc when we are using the prove by Induction method. When we use Repertoire method, we guess for f(n) and *find* A(n), B(n) etc);
"this gives us a repertoire of special cases that we can solve" (the special cases are the independent equations in the unknowns A(n),B(n),C(n) and solving them gives us the values of A(n) etc).
"Then we obtain the general case" (the solution of recurrence [1], the general value of f(n) )
"by combining the special cases" (In this case we combine the solutions of the equations which are the "special cases").
Hopefully that helped a bit.
The repertoire method pops up all over CM in various contexts, and once you grasp it is easy to identify and use. Enjoy the rest of Concrete Mathematics (which imho is a great, great book every programmer should have on his bookshelf)
When I originally worked through the book I couldn't make head or tail of the "repertoire method" of solving recurrences. Eventually I did figure it out and sometime later I wrote up what I understood and posted it on my (then) blog. It seems that a lot of people search for "Concrete Mathematics Repertoire method" on Google and it is my second most popular blog post (The most popular post is this one, fwiw)
So I re-read the repertoire method post today and while it is correct, I can explain it better today so here goes.
(What follows may not make sense to you if you are not working through CM (be warned!). Also be warned that I have no formal training in mathematics, computer science or programming and am entirely self taught. So people with such training can probably explain things better. The following reflects only *my* understanding. That said, onwards!)
By the time you hit the repertoire method section in Chapter 1 of Concrete Mathematics, you have been taught a simple method to find closed forms of recurrences. The essential algorithm is
(a) make a table of the recurrence values R(n) for small values of n.
(b) Eyeball the table to see if you can spot a pattern,
(c) write down the pattern.
(d) Prove (or disprove) the candidate closed form's correctness by Mathematical Induction over (a subset of) the natural numbers.
You used this method, for example to solve the Josephus problem, so you know where to stand (in the circle of your idiot friends trying to commit mass suicide) so that you end up being the survivor), surrender to the Romans and become a historian for the ages).
The repertoire method makes its (first) appearance in the generalization of the Josephus recurrence. The constants 1 and -1 are replaced by alpha beta and gamma to give the more general recurrence
f(1) = alpha
f(2n) = 2*f(n) + beta
f(2n + 1) = 2*f(n) + gamma~~~~~~~~~~~~~~~~~~~~~~~[1]
Your job is to find f(n) such that this recurrence is true for any values of alpha, beta, and gamma.
So how do you do this? You use the only technique you know (at this point in the book) of making a table for small values of n and eyeballing it to spot a pattern (I am too lazy to reproduce the table here, go buy the book!). You don't spot a pattern for the f(n) but you do notice that all values of f(n) follow a pattern of
f(n) = A(n)*alpha + B(n)*beta + C(n)*gamma~~~~~~~~~~~~~~[2]
This is a kind of template of what the final closed form will look like, depending of course on the values of A(n), B(n) etc
In other words if we can find functions A(n), B(n) and C(n) such that when given n they generate the right coefficients as in Table 1.12, then we have a closed form for f(n).
Something very important happened here. You broke down a problem into smaller subproblems.
You still don't know the value of f(n) but now you know that if you can find the values of the functions A(n), B(n), and C(n) you have solved f(n).
Now you can find these values with your trusted "spot a pattern and verify with induction" (the only tool you have at this point) OR you can use the (unexplained!) repertoire method.
The first bit of confusion arises because the authors do both. They guess values of all the three functions in n, A(n), B(n) and C(n) from the initial table, say (correctly) that proving that these values by induction is long and tedious and then they go ahead and prove that the guessed value of A(n) is correct by induction! (to be fair they are solving for only A(n) and not all the unknowns simultaneously but though smaller this induction is still tedious. Try it. I did.)
Or, in more detail,
a value is guessed, (that A(n) = 2^m , m coming from rewriting n as 2^m + k as in the original Josephus problem - the book uses the letter l instead of k, I use k to distinguish easily from the number 1), beta and gamma are set to zero (remember the recurrence has to hold for *all* values of alpha, beta and gamma, including the selected 1,0,0) and then the recurrence [1] is rewritten (using [2]) as a recurrence in terms of A(n).
I'll repeat that so it is clear what is happening
Step 1: Guess a value for A(n), by eyeballing.We guess A(n) = 2^m
Step 2: Select alpha, beta and gamma so that the other two functions of n, B(n) and C(n), get eliminated from [2]. You can do this by selecting alpha = 1 and beta = gamma = zero.
Step 3: Rewrite the equation [2] (i.e the observed generalized form) in terms of the selected values of alpha, beta and gamma. You get f(n) = A(n).
Step 4: Use this equation (ie f(n) = A(n)) and your chosen values of alpha, beta and gamma to rewrite the original recurrence (ie equation [1]) to get
A(1) = 1 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~[3]
A(2n) = 2*A(n)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~[4]
A(2n + 1) = 2*A(N)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~[5]
Now the problem becomes to prove that your guess (i.e, A(n) = A(2^m + k) = 2^m) satisfies this new recurrence as expressed by [3] and [4] and [5].
The authors state "Sure enough it is true (by induction on m) that A(2^m + k) = 2^m "
The authors don't show the induction but you can work out this (tedious but not difficult) induction. Only basic algebraic manipulation is required)
Be aware that (a) the induction is on m, not n and (b) the predicate to be proven has the form P_m: (A(2^m +k) => [3] AND [4] AND [5]).
First, prove P_zero (as m starts from zero, though n starts from 1 - we need an induction on m, not n!). Then prove that P_m => P_m+1. (Weak Induction is sufficient).
So we prove (yay!!) that A(n) does = 2^m.
You could do the same for B(n) and C(n). Select values for alpha, beta and gamma to create recurrences in terms of B(n) only and then C(n) only, just as we did above for A(n), then use mathematical induction over m to prove your guesses correct.
In the book though, the authors switch to the repertoire method to find B(n) and C(n). This switch is the first confusing bit - A(n) is found using a guess + induction (the old method - eyeball, guess, use induction). But then they switch - and the repertoire method is used to find B(n) and C(n) and the initial guesses as to their values are unused!
Worsening the confusion is the fact that the repertoire method is not identified or explained explicitly at this point. As a student states in a margin note (great idea btw) "Beware: the authors are expecting you to figure out the idea of the repertoire method from seats of pants examples instead of giving a top down presentation"
The seat-of-pants example is actually enough if A(n),B(n) and C(n) are all worked out with the repertoire method.
So let us solve the whole thing with the repertoire method (no induction) and see how it works. Let us throw away the guesses about the values of A(n), B(n), and C(n). We'll assume we couldn't make any guesses for A(n), B(n) and C(n).
All we have is the original recurrence
f(1) = alpha
f(2n) = 2*f(n) + beta
f(2n + 1) = 2*f(n) + gamma~~~~~~~~~~~~~~~~~~~~~[1]
and our observation that f(n) always has the form
f(n) = A(n)*alpha + B(n)*beta + C(n)*gamma~~~~~~~~[2]
ok so we don't know (and we need to find out) the values of A(n), B(n) and C(n) .
The repertoire method (for this recurrence) works like this.
(1) Guess a value for f(n). (ie the guess is for the whole of [2] NOT a component A(n) as we did above!)
(2)See if you can find values for alpha, beta and gamma to validate this guess. Rewrite [1], the original recurrence in terms of your guess for f(n). See if you can find values for alpha, beta and gamma.
(3) Substitute these values (of alpha, beta and gamma), back into [2]. You'll get an equation in terms of the three unknowns A(n), B(n) and C(n).
(4)Repeat steps (1) - (3) till you have three independent equations.
(5)Solve for three linear equations in three unknowns.
Done.
Important: If you make a "wrong" guess you will end up with a useless equation like 0 = 0 or an equation that is not independent of the already derived equations and so on. If this happens, don't worry about it, try another guess till you do get three independent equations.
In detail.
I guess (the authors do too) that f(n) = 1.
Rationale for the guess: f(n) = constant is the simplest possible formulation of f(n) (just for fun you might want to try f(n) = 0)
Let us try substituting this in [1]
f(1) = alpha becomes 1 = alpha (since f(n) is 1 for any n).
similarly
f(2n) = 2*f(n) + beta becomes 1 = 2*1 + beta so beta = -1
f(2n + 1) = 2*f(n) + gamma becomes 1 = 2*1 + gamma so gamma = -1
so we have values for alpha,beta, gamma and f(n) and when we substitute back into [2] we get
A(n) - B(n) - C(n) = 1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~[6]
ok!!! we have the first equation.
Now if we could get just two more independent equations like this we would have three equations in three unknowns (and so solve by Linear Algebra).
The authors use f(n) = n as their second guess and get A(n) + C(n) = n as their second equation.
(This is a good guess too. After f(n) = k, f(n) = n is the next rung up the complexity ladder. But in this specific example we can do better - see below)
and since they already proved that A(n) = 2^m by the "guess and use induction" method they don't need a third equation. They have two equations in two unknowns and they solve to get the solution.
But we don't have any guesses as to the values of A(n), so we can't plug that in.
We guessed at f(n) = 1 and got the equation A(n) - B(n) - C(n) = 1 and we need two more independent equations. We could re use the authors' f(n) = n guess and also cheat a bit and reuse the (non generalized) Josephus recurrence solution that we already proved that to "guess" that f(n) = 2k + 1. Then alpha = 1, beta = -1 and gamma = 1, giving us the third equation A(n) - B(n) + C(n) = 2k + 1. Three equations three variables. Solve. This gives the right answer too.
But that feels like a cheat. What if we hadn't solved the Josephus recurrence before? How would we guess f(n) = 2k + 1? We could go with f(n) = n but we can do better.
Since n = 2^m + k, we guess (our second guess)
f(n) = 2^m
and f(n) = k. (our third guess)
(Rationale for these guesses. Since n is dependent on 2^m and k why not guess with the simpler variables rather than f(n) = n, like the example in the book does? In this case this decision pays off spectacularly, giving the solutions for A(n) and C(n) directly and B(n) trivially )
These give us the equations, (just like we worked out [4] above, try it!)
A(n) = 2^m~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~[7]
C(n) = k~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~[8]
and these two along with [6] give us B(n) = 2^m - k - 1.
Look ma! no induction !
So now we have the values for A(n), B(n) and C(n) and now we can say that
the solution to the recurrence
f(1) = alpha
f(2n) = 2*f(n) + beta
f(2n + 1) = 2*f(n) + gamma is (given n = 2^m + k as explained earlier in the book)
f(n) = (2^m)*alpha + (2^m - k - 1)*beta + k*gamma.
Double checking,When alpha = 1, beta = -1 and gamma = 1 we get
the solution to
f(1) = 1
f(2n) = 2*f(1) - 1
f(2n + 1) = 2*f(n) + 1 (note: this is the original Josephus Recurrence)
is (2^m)*1 + (2^m - k - 1)*(-1) + k*(1), which resolves to
2k+1 which agrees with [1.9] (in the book).
Hopefully now what the authors say about the recurrence method makes more sense, though the sentence structure at this point in the book is confusing Let us take it apart - my comments in italics.
"First we find settings for parameters for which we know the solution" (the parameters here are alpha beta and gamma, the "solution"s are the various guessed values of f(n) NOT A(n),B(n), C(n). We make guesses for A(n),B(n) etc when we are using the prove by Induction method. When we use Repertoire method, we guess for f(n) and *find* A(n), B(n) etc);
"this gives us a repertoire of special cases that we can solve" (the special cases are the independent equations in the unknowns A(n),B(n),C(n) and solving them gives us the values of A(n) etc).
"Then we obtain the general case" (the solution of recurrence [1], the general value of f(n) )
"by combining the special cases" (In this case we combine the solutions of the equations which are the "special cases").
Hopefully that helped a bit.
The repertoire method pops up all over CM in various contexts, and once you grasp it is easy to identify and use. Enjoy the rest of Concrete Mathematics (which imho is a great, great book every programmer should have on his bookshelf)
Subscribe to:
Posts (Atom)