Tuesday, November 12, 2013

On reading proofs


Paul Halmos on reading a proof
Don't just read it; fight it! Ask your own questions, look for your
own examples, discover your own proofs. Is the hypothesis necessary?
Is the converse true? What happens in the classical special case? What
about the degenerate cases? Where does the proof use the hypothesis?

Don’t sneer at ideas that save you twenty percent

Knuth says in "coders at work" at page 580
Combinatorial algorithms are fascinating because one good idea can save
you ten orders of magnitude in running time. But I don’t sneer at ideas that
save you twenty percent when you’re doing it a trillion times. Because if you
can save a hundred nanoseconds in a loop that’s being done a trillion times,
I think you’re saving a day. If the code is going to be used a lot it can really
pay off so you’ve got to go to subtle tricks that aren’t easy to understand.

Tuesday, July 16, 2013

Dynamic Programming as algorithm design is 60 year old

It is now more than 60 years, Dynamic Programming has been in use. Belman said:
“I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.”
 What are these activities?