秋風とアルゴリズム入門

土曜日に有楽町へ出かけようと思っていました。金曜日の夜中というか土曜日の朝かという時間に目が覚めました。熱が出ました。というわけで、安静のために土日を充てました。ふぅ。

暇はヒマなのですが、論文を読んだりプログラムを書いたりするような、ちょっと考える作業をしようという気分にはなれませんでした。なので、Introduction to Algorithms 3rd ed. が届いていたので、目次を眺めて変更点をリストする作業をしました。

別に本が届かなくても、webで3rdと2ndの目次は公開されています。それから、Charles Leiserson教授の動画は少しだけ面白かったです。とりあえず、私は20章と27章を読んどいて下さい。

目にとまる変更点は、新たに加わった van Emde Boas Trees と Multithreaded Algorithms (sample pdf) だと思います。Transdichotomous (/word-RAM) モデルや Google Map Reduce、はやってますものね。すぐ読みたかったのですが、高熱で関節が痛いし、重いんですよ本が。

以下は、目次の変更点のリストです。内容の差異は、まだぜんぜん知りません。

I Foundation

• 第4章に、二つの節（4.1 The maximum-subarray problem と 4.2 Strassen's algorithm for matrix multiplication） が加わって、Recurrences から Divide-and-Conquire に表題が変わった。

IV Advanced Design and Analysis Techniques

• 第15章(DP)の第1節が、Assembly-line scheduling から Rod cutting に変わった。
• 第16章(Greedy)の第4節が、Theoretical foundations for greedy methods から Matroids and greedy methods に変わった。

V Advanced Data Structures

• Binomial Heaps の章が無くなり、van Emde Boas tree が新設。

VII Selected Topics

• 第27章が、Sorting Networks から Multithreaded Algorithms へ変更。
• 第 28 章にあった、Matrix Operations の構成の変更。Properties of matrices が付録へ。Strassen's algorithm for matrix multiplication が第4章へ。

おしまい。