We just discovered that the minimal solution to our problem is formed out of minimal solutions to the subproblems.
Here's a question I should have explored from the beginning: How big is our solution space ? In other words, how many BST's can we construct from a sequence {1,..., n} ?
Stumbled upon this interview with this year's winner of the TopCoder contest. Fascinating. I admire people who can think under pressure. I never could do that. I looked at the problems and I decided to give the hardest one a try. I gave myself unlimited time and resources (I was allowed to hit the books).
Here's the problem.
Read on to find out about my vagaries and the eventual discovery of the solution.
My favorite book is
The Pleasure of Finding Things Out and the Meaning of It All
by Richard P. Feynman
His clarity, honesty, brilliance and humor shine through in all the pieces in the book and it is just a joy to read him.
To tickle your curiosity here's some ideas out of his essay about the relationship between science and religion.
Religion provides a moral and ethical framework to society and that is great. Religion also has an inspirational role in people's lives and that is great also. But religion as a way to explain the world surrounding us is too simplistic and inflexible. Everything is set in stone and is based on belief. There's not much room for doubt. If new facts or observations turn up that would make other explanations more plausible they' re ignored or suppressed.
Science on the other hand is the total opposite: in constant change. Observing the world around us suddenly is much more fun. New observations and experiments can lead to new explanations that completely overhaul what was thought before. We are slowly moving forward that way, searching for truth, understanding our world better. Will we ever know everything ? Probably not, but that shouldn't stop us from continuing. The good news is that we will never run out of things to explore.
Note though for science to function and to stay healthy it needs honest scientists and there's an essay about that in the book too.
Looks like movable types needs more than one entry for me to test the looks of the blog. I might as well start by introducing myself as this seems like a polite thing to do.
I'm in my thirties, happily married, living near San Francisco, almost with ocean view. I'm originally from Germany, studied computer science there and now I earn a living in a big software company in the Bay Area. I'm a decent basketball player and a walking NBA dictionary.
I just started this blog because I hope blogging will force me into more discipline and will help me make progress with the things I like to accomplish in my spare time. The lofty goal is to slowly re-read the math and cs courses from college I long ago have forgotten. Along the way I also want to pick up Haskell. I'm a recovering Java Junkie and I feel I need a new mindset, an intellectual change of scenery.
This is the obligatory test entry. I just installed mt and it seems like the css style I chose needs an entry to display the things correctly.
