演算法設計

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　常用的數學定理