Jeff Erickson's Algorithms, Etc.
イリノイ大学のJeff氏が、アルゴリズムに関するいろいろな文書を我々に公開してくれている。それぞれについてポインタを示したい。
Algorithms Notes
講義ノートは６＋１の章に分かれている。それぞれ：
- 再帰
- 無作為化
- 償却解析
- 基礎グラフアルゴリズム
- 組合せ最適化
- 困難性
そして
- 追補
Recursion (再帰) (119 pages)
| No | PDFファイルタイトル | 内容 | 競技プログラミング的に重要か？ | |
|---|---|---|---|---|
| 1 | 単純化と委譲 | o | ||
| 2 | 高速フーリエ変換 | x | ||
| 3 | バックトラック法 | o | ||
| 4 | 速度の早い指数時間のアルゴリズム | o | ||
| 5 | 動的計画法 | フィボナッチ数、最長増加部分列 | o | |
| 6 | 応用的な動的計画法の手法 | o | ||
| 7 | 貪欲法 | o | ||
| 8 | マトロイド | ? |
Randomization (無作為化) (69 pages)
| No | PDFファイルタイトル | 競技プログラミング的に重要か？ | |
|---|---|---|---|
| 9 | ナットとボルト（ランダム化クイックソート） | o | |
| 10 | ツリープとスキップリスト | o | |
| 11 | ※訳せず… | ? | |
| 12 | ハッシュ化 | o | |
| 13 | 文字列一致 | o | |
| 14 | ランダム最小カット | o |
Amortization (償却解析) (44 pages)
Basic graph algorithms (基礎グラフアルゴリズム) (66 pages)
19. 表現と探索