演算法設計

　　本書討論很多網路演算法方面的主題，也在其他章節安排了傳統演算法的網路應用程式範例並已預設提供給有一定程度的學生。本書中全部演算法仍是以高階「虛擬碼」寫成，只有在選讀的Java實作範例章節中，才以特定語言寫出程式。並在第一章中復習包括指數、對數與級數，且將其他實用的數學事實 (包括基本機率) 整理在附錄A中。

本書特色

　　■演算法設計模式可提供設計演算法的清晰方法。
　　■視覺化證明可幫助讀者直覺且精確地了解數學論證。
　　■網路範例可引起讀者對網路應用程式所採用傳統及新演算法的學習興趣，例如雜湊、封包路由、密碼學及更多主題。
　　■選讀的Java程式碼章節提供具體的實作範例。
　　■使用隨機技巧可使原本需要設計精巧資料結構、進行複雜的平均狀況分析之處，取代以簡單的資料結構及演算法，分析也變得直覺。
　　■本書網站 (www.wiley.com/college/goodrich) 提供輔助資料給學生及教師，包括線上投影片、習題提示、題庫、Java程式碼及更多資源。

Part I　演算法分析

第1章　演算法分析
1.1 　演算法分析方法論
1.2　漸進表示法
1.3　相關數學速覽
1.4　演算法分析實例
1.5　攤銷分析
1.6　實驗方法
1.7　習題

第2章　基本資料結構
2.1　堆疊和佇列
2.2　Vectors、Lists和Sequences
2.3　樹
2.4　優先權佇列與堆積
2.5　字典與雜湊表
2.6　Java範例：堆積
2.7　練習

第3章　搜尋樹與跳躍串列
3.1　有序字典和二元搜尋樹
3.2　AVL 樹
3.3　有限深度搜尋樹
3.4　外張樹
3.5　跳躍串列
3.6　Java範例：AVL和紅黑樹
3.7　習題

第4章　排序、集合與選擇2
4.1　合併排序
4.2　抽象資型態集合
4.3　快速排序
4.4　比較式排序的下限
4.5　桶子排序與基底排序
4.6　排序演算法的比較
4.7　挑選
4.8　Java 範例：原位的快速排序
4.9　習題

第5章　基本技巧
5.1　貪婪演算法
5.2　各個擊破 (Divide-and-Conquer)
5.3　動態規劃
5.4　習題

Part II　圖形演算法

第6章　圖
6.1　圖的抽象資料型態
6.2　圖的資料結構
6.3　圖形走訪
6.4　有向圖
6.5　Java範例：深度優先搜尋
6.6　習題

第7章　加權圖
7.1　單一源點的最短路徑
7.2　完全配對最短路徑
7.3　最小生成樹
7.4　Java範例：Dijkstra演算法
7.5　習題

第8章　網路流與配對
8.1　網路流與切割
8.2　最大網路流
8.3　最大二分配對
8.4　最低成本網路流
8.5　Java範例：最低成本網路流
8.6　習題

Part III　網路演算法

第9章　文字處理
9.1　字串與樣式比對演算法
9.2　Trie樹
9.3　文字壓縮
9.4　文字相似性測試
9.5　習題

第10章　數論與密碼學
10.1　關於數字的基礎演算法
10.2　密碼計算
10.3　資訊安全演算法及協定
10.4　快速傅利葉轉換
10.5　Java範例：FFT
10.6　習題

第11章　網路演算法
11.1　複雜度測量與模型
11.2　基本分散式演算法
11.3　路由廣播與單路由傳輸
11.4　群播路由
11.5　習題

Part IV　進階主題

第12章　計算幾何學
12.1　範圍樹
12.2　優先搜尋樹
12.3　四元樹及-d樹
12.4　平面掃描技術
12.5　凸多邊形包覆
12.6　Java範例：凸多邊形包覆
12.7　習題

第13章　NP-Complete
13.1　P與NP
13.2　NP-Completeness
13.3　重要的NP-Complete問題
13.4　近似演算法
13.5　回溯及分支限制
13.6　習題

第14章　演算架構
14.1　外部記憶體演算法
14.2　平行演算法
14.3　線上演算法
14.4　習題

附錄A　常用的數學定理