ezyang's blog

the arc of software bends towards understanding

Blog name changed...

October 27, 2010

…because I don’t live in a room numbered 245s anymore. Yep. :-)

image

This is a cow. They munch grass next to the River Cam.

Pop quiz. What do matrix-chain multiplication, longest common subsequence, construction of optimal binary search trees, bitonic euclidean traveling-salesman, edit distance and the Viterbi algorithm have in common?

6 Comments

  1. Julien Oster
    You can find an optimum using dynamic programming?
  2. spang
    Man, and I thought there was some significance to “245 seconds”. Wrong!
  3. gwern
    Oh, I know this one! They are all computable!
  4. phurst
    They’re CS concepts!
  5. Jose
    What do they have in common?
  6. Edward Z. Yang
    It’s dynamic programming. :-)