算法設計

本書是近年來關於算法設計和分析的不可多得的優秀教材。本書覆蓋的面較寬，凡屬串行算法的經典論題都有涉及，並且論述深入有新意。全書共200多道豐富而精彩的習題是本書的重要組成部分，也是本書的突出特色之一。 ^[2] 

以各種算法設計技術（如貪心法、分治策略、動態規劃、網絡流、近似算法、隨機算法等）為主線來組織素材，突出了算法設計的思想和分析的基本原則，為從事實際問題的算法設計與分析工作提供了清晰的、整體的思路和方法。

本教材內容非常豐富，不但深入系統地闡述了算法設計與分析的理論，而且給出了大量的典型範例和參考文獻。

本教材以算法為主線來處理算法與數據結構的關係。這種安排突出了算法設計的中心思想，避免了與數據結構課程在內容上的重複，更加適合於國內的教學計劃。

本教材的敍述和選材非常適合教學。內容由淺入深，由具體到抽象，從算法設計技術與分析方法自然過渡到計算複雜性理論，選配了大量難度適當的練習，並給出求解範例。

第1章　引言：某些典型的問題

1.1　第一個問題：穩定匹配

1.2　五個典型問題

帶解答的練習

練習

註釋和進一步的閲讀

第2章　算法分析基礎

2.1　計算可解性

2.2　增長的漸近階

2.3　用表和數組實現穩定匹配算法

2.4　一般運行時間的概述

2.5　更復雜的數據結構：優先隊列

帶解答的練習

練習

註釋和進一步的閲讀

第3章　圖

3.1　基本定義與應用

3.2　圖的連通性與圖的遍歷

3.3　用優先隊列與棧實現圖的遍歷

3.4　二分性測試：寬度優先搜索的一個應用

3.5　有向圖中的連通性

3.6　有向無圈圖與拓撲排序

帶解答的練習

練習

註釋和進一步的閲讀

第4章　貪心算法

4.1　區間調度：貪心算法領先

4.2　最小延遲調度：一個交換論證

4.3　最優高速緩存：一個更復雜的交換論證

4.4　一個圖的最短路徑

4.5　最小生成樹問題

4.6　實現Kruskal算法：Unoin－Find數據結構

4.7　聚類

4.8　Huffman碼與數據壓縮

4.9　最小費用有向樹：一個多階段貪心

帶解答的練習

練習

註釋和進一步的閲讀

第5章　分治策略

5.1　第一個遞推式：歸併排序算法

5.2　更多的遞推關係

5.3　計數逆序

5.4　找最接鄰近的點對

5.5　整數乘法

5.6　卷積與快速傅里葉變換

帶解答的練習

練習

註釋和進一步的閲讀

第6章　動態規劃

6.1　帶權的區間調度：一個遞歸過程

6.2　動態規劃原理：備忘錄或者子問題迭代

6.3　分段的最小二乘：多重選擇

6.4　子集和與揹包：加一個變量

6.5　RNA二級結構：在區間上的動態規劃

6.6　序列比對

6.7　通過分治策略在線性空間的序列比對

6.8　圖中的最短路徑

6.9　最短路徑和距離向量協議

6.10　圖中的負圈

帶解答的練習

練習

註釋和進一步的閲讀

第7章　網絡流

第8章　Ng與計算的難解性

第9章　一個超出

第10章　擴展易解性的界限

第11章　近似算法

第12章　局部搜索

第13章　隨機算法

後記：永不停止運行的算法

索引