算法設計與分析習題解答（第3版）

《算法設計與分析習題解答（第3版）》是2014年清華大學出版社出版的圖書，作者是王曉東。

編輯推薦

本書是《算法設計與分析（第3版）》（ISBN: 9787302348641）配套的輔助教材，對主教材中的全部習題做了詳盡的解答，並提供了套用實驗型習題的全部測試數據。
本書的內容是對主教材深入的擴展，許多主教材中無法講述的較深入的主題通過習題的形式展現出來。
為了加強學生靈活運用算法設計策略解決實際問題的能力，本書將主教材中的許多習題改造成算法實現題，要求學生不僅設計出解決具體問題的算法，而且能上機實現。教學實踐反映這類算法實現題的教學效果非常好。
作者還結合國家精品課程建設，進行了教材的立體化開發，包括主教材、輔助教材、實驗與設計、電子課件和教學網站建設。
本書內容豐富，觀點新穎，理論聯繫實際。不僅可用作高等院校計算機科學與工程專業本科生和研究生學習計算機算法設計的輔教教材，而且也適合廣大工程技術人員和自學讀者學習參考。
本書是學習算法設計與分析的經典教材學習輔導用書，清華大學出版社配套開發了豐富的線上教學資源，可以在清華大學出版社的線上教學平台上進行練習與測試，實現教學互動、智慧型學習。另外配有主教材《算法設計與分析（第3版）》（ISBN: 9787302348641）。本書的PPT電子教案、配套的原始碼等資源，可到清華大學出版社官網下載。
本教材可適用於國內大多數普通高校計算機及相關專業算法設計與分析課程教學的需要。從2004年8月本書第1版出版到2007年底，共重印了10餘次，第2版已經重印了10餘次，已經被國內一百餘所大學的本科生和研究生選作教材。

內容簡介

本書是清華大學出版社出版的普通高等教育“十一五”國家級規劃教材《算法設計與分析（第3版）》(主教材)配套的輔助教材，對《算法設計與分析（第3版）》一書中的全部習題做了詳盡的解答。本書內容是對《算法設計與分析（第3版）》的較深入的擴展，許多在主教材中無法講述的、較深入的主題通過習題的形式展現出來。為了加強學生靈活運用算法設計策略解決實際問題的能力，本書將主教材中的許多習題改造成算法實現題，要求學生不僅設計出解決具體問題的算法，而且能夠上機實現。作者的教學實踐反映出這類算法實現題的教學效果非常好。作者還結合國家精品課程建設，進行了教材的立體化開發，包括主教材、輔助教材、實驗與設計、電子課件和教學網站建設。

本書內容豐富，觀點新穎，理論聯繫實際。不僅可以用作高等學校計算機科學與技術學科各專業本科生和研究生學習計算機算法設計的輔助教材，而且也適合廣大工程技術人員和自學讀者學習參考。

作者簡介

王曉東，1957年3月出生，福州大學計算機系教授，福建省計算機學會理事長。研究領域是算法設計與算法評價，基於計算機網路和信息安全的大規模問題求解算法與數據結構，信息可視化技術，幾何計算，並行和分散式算法設計，計算複雜性理論。先後主持了和算法設計與分析有關的國家自然科學基金項目、國家優秀留學回國人員基金項目、福建省傑出人才基金項目和省自然科學基金項目等7個研究課題；獲得國家科技進步二等獎1項，省科技進步二等獎3項。主持國家精品課程“算法與數據結構”和“算法設計與分析”的課程建設，獲福建省教學成果一等獎。在國內外重要學術刊物上發表有創見性的論文50餘篇；出版《算法設計與分析》等學術著作7部，在算法複雜性研究方面取得了一系列理論研究和套用成果。例如，在對著名的凸殼問題的計算複雜性研究成果中推廣了關於判定樹模型下問題的計算複雜性下界著名的Ben-Or定理，並套用於分析凸殼問題的計算複雜性，在較一般的情況下改進和完善了國際算法界知名學者Aggarwal、Steele和Yao等提出的關於凸殼問題計算複雜性下界的結果。研究成果得到國內外同行專家的好評並被國內專業刊物所引用。

圖書目錄

第1章算法引論1

習題11實參交換1

習題12方法頭簽名1

習題13數組排序判定1

習題14函式的漸近表達式2

習題15O(1)和O(2)的區別2

習題16按漸近階排列表達式2

習題17算法效率2

習題18硬體效率2

習題19函式漸近階3

習題110n!的階3

習題111平均情況下的計算時間複雜性3

算法實現題11統計數字問題4

算法實現題12字典序問題5

算法實現題13最多約數問題6

算法實現題14金幣陣列問題7

算法實現題15最大間隙問題10

第2章遞歸與分治策略12

習題21Hanoi 塔問題的非遞歸算法12

習題227個二分搜尋算法13

習題23改寫二分搜尋算法16

習題24大整數乘法的O(nmlog(3/2))算法16

習題255次n/3位整數的乘法16

習題26矩陣乘法18

習題27多項式乘積18

習題28不動點問題的O(logn)時間算法19

習題29主元素問題的線性時間算法19

習題210無序集主元素問題的線性時間算法19目錄算法設計與分析習題解答（第3版）習題211O(1)空間子數組換位算法20

習題212O(1)空間合併算法22

習題213n段合併排序算法28

習題214自然合併排序算法28

習題215最大值和最小值問題的最優算法30

習題216最大值和次大值問題的最優算法31

習題217整數集合排序31

習題218第k小元素問題的計算時間下界31

習題219非增序快速排序算法32

習題220隨機化算法33

習題221隨機化快速排序算法33

習題222隨機排列算法33

習題223算法qSort中的尾遞歸33

習題224用棧模擬遞歸34

習題225算法select中的元素劃分34

習題226O(nlogn)時間快速排序算法35

習題227最接近中位數的k個數35

習題228X和Y的中位數35

習題229網路開關設計36

習題230帶權中位數問題37

習題231構造Gray碼的分治算法38

習題232網球循環賽日程表39

算法實現題21輸油管道問題43

算法實現題22眾數問題44

算法實現題23郵局選址問題45

算法實現題24馬的Hamilton週遊路線問題45

算法實現題25半數集問題53

算法實現題26半數單集問題54

算法實現題27士兵站隊問題55

算法實現題28有重複元素的排列問題56

算法實現題29排列的字典序問題57

算法實現題210集合劃分問題（一）59

算法實現題211集合劃分問題（二）60

算法實現題212雙色Hanoi塔問題61

算法實現題213標準二維表問題63

算法實現題214整數因子分解問題63

算法實現題215有向直線2中值問題64

第3章動態規劃67

習題31最長單調遞增子序列67

習題32最長單調遞增子序列的O(nlogn)算法68

習題33漂亮列印69

習題34整數線性規劃問題70

習題35二維背包問題70

習題36Ackermann函式71

算法實現題31獨立任務最優調度問題73

算法實現題32最少硬幣問題75

算法實現題33序關係計數問題76

算法實現題34多重冪計數問題76

算法實現題35編輯距離問題77

算法實現題36石子合併問題78

算法實現題37數字三角形問題80

算法實現題38乘法表問題81

算法實現題39租用遊艇問題82

算法實現題310汽車加油行駛問題83

算法實現題311圈乘運算問題84

算法實現題312最少費用購物89

算法實現題313最大長方體問題92

算法實現題314正則表達式匹配問題93

算法實現題315雙調旅行售貨員問題96

算法實現題316最大k乘積問題98

算法實現題317最小m段和問題100

算法實現題318紅黑樹的紅色內結點問題101

第4章貪心算法109

習題41活動安排問題的貪心選擇109

習題42背包問題的貪心選擇性質109

習題43特殊的01背包問題110

習題44程式最優存儲問題110

習題45最優裝載問題的貪心算法110

習題46Fibonacci序列的Huffman編碼111

習題47最優前綴碼的編碼序列111

習題48任務集獨立性問題111

習題49矩陣擬陣111

習題410最小權最大獨立子集擬陣112

習題411整數邊權Prim算法112

習題412最大權最小生成樹112

習題413最短路徑的負邊權113

習題414整數邊權Dijkstra算法113

算法實現題41會場安排問題113

算法實現題42最優合併問題115

算法實現題43磁帶最優存儲問題115

算法實現題44磁碟檔案最優存儲問題116

算法實現題45程式存儲問題117

算法實現題46最優服務次序問題118

算法實現題47多處最優服務次序問題119

算法實現題48d森林問題120

算法實現題49汽車加油問題121

算法實現題410區間覆蓋問題122

算法實現題411硬幣找錢問題123

算法實現題412刪數問題123

算法實現題413數列極差問題124

算法實現題414嵌套箱問題124

算法實現題415套匯問題126

算法實現題416信號增強裝置問題127

算法實現題417磁帶最大利用率問題128

算法實現題418非單位時間任務安排問題129

算法實現題419多元Huffman編碼問題131

算法實現題420多元Huffman編碼變形132

算法實現題421區間相交問題134

算法實現題422任務時間表問題134

第5章回溯法136

習題5\|1裝載問題改進回溯法（一）136

習題5\|2裝載問題改進回溯法（二）137

習題5\|301背包問題的最優解137

習題5\|4最大團問題的疊代回溯法138

習題5\|5旅行售貨員問題的費用上界139

習題5\|6旅行售貨員問題的上界函式141

算法實現題5\|1子集和問題141

算法實現題5\|2最小長度電路板排列問題142

算法實現題5\|3最小重量機器設計問題145

算法實現題5\|4運動員最佳匹配問題146

算法實現題5\|5無分隔設定字典問題147

算法實現題5\|6無和集問題149

算法實現題5\|7n色方柱問題150

算法實現題5\|8整數變換問題154

算法實現題5\|9拉丁矩陣問題155

算法實現題5\|10排列寶石問題157

算法實現題5\|11重複拉丁矩陣問題159

算法實現題5\|12羅密歐與朱麗葉的迷宮問題161

算法實現題5\|13工作分配問題163

算法實現題5\|14獨立鑽石跳棋問題164

算法實現題5\|15智力拚圖問題170

算法實現題5\|16布線問題177

算法實現題5\|17最佳調度問題178

算法實現題5\|18無優先權運算問題179

算法實現題5\|19世界名畫陳列館問題181

算法實現題5\|20世界名畫陳列館問題（不重複監視）184

算法實現題5\|21部落衛隊問題186

算法實現題5\|22蟲蝕算式問題188

算法實現題5\|23完備環序列問題191

算法實現題5\|24離散01串問題193

算法實現題5\|25噴漆機器人問題195

算法實現題5\|26n2-1謎問題197

第6章分支限界法204

習題6\|101背包問題的棧式分支限界法204

習題6\|2用最大堆存儲活結點的優先佇列式分支限界法206

習題6\|3團頂點數的上界209

習題6\|4團頂點數改進的上界209

習題6\|5修改解旅行售貨員問題的分支限界法209

習題6\|6解旅行售貨員問題的分支限界法中保存已產生的排列樹211

習題6\|7電路板排列問題的佇列式分支限界法213

算法實現題6\|1最小長度電路板排列問題(一)214

算法實現題6\|2最小長度電路板排列問題(二)217

算法實現題6\|3最小權頂點覆蓋問題220

算法實現題6\|4無向圖的最大割問題223

算法實現題6\|5最小重量機器設計問題226

算法實現題6\|6運動員最佳匹配問題228

算法實現題6\|7n後問題230

算法實現題6\|8圓排列問題232

算法實現題6\|9布線問題234

算法實現題6\|10最佳調度問題236

算法實現題6\|11無優先權運算問題239

算法實現題6\|12世界名畫陳列館問題241

算法實現題6\|13騎士征途問題244

算法實現題6\|14推箱子問題245

算法實現題6\|15圖形變換問題250

算法實現題6\|16行列變換問題253

算法實現題6\|17重排n2宮問題254

算法實現題6\|18最長距離問題258

第7章機率算法264

習題71模擬常態分配隨機變數264

習題72隨機抽樣算法265

習題73隨機產生m個整數265

習題74集合大小的機率算法266

習題75生日問題266

習題76易驗證問題的拉斯維加斯算法267

習題77用數組模擬有序鍊表268

習題78O(n3/2)舍伍德型排序算法268

習題79n後問題解的存在性268

習題710整數因子分解算法269

習題711非蒙特卡羅算法的例子270

習題712重複3次的蒙特卡羅算法271

習題713集合隨機元素算法271

習題714由蒙特卡羅算法構造拉斯維加斯算法272

習題715產生素數算法273

習題716矩陣方程問題273

算法實現題71模平方根問題274

算法實現題72集合相等問題275

算法實現題73逆矩陣問題276

算法實現題74多項式乘積問題277

算法實現題75皇后控制問題277

算法實現題763SAT問題280

算法實現題77戰車問題281

算法實現題78圓排列問題283

算法實現題79騎士控制問題284

算法實現題710騎士對攻問題285

第8章NP完全性理論287

習題81RAM和RASP程式287

習題82RAM和RASP程式的複雜性287

習題83計算nn的RAM程式287

習題84沒有MULT和DIV指令的RAM程式289

習題85MULT和DIV指令的計算能力289

習題86RAM和RASP的空間複雜性289

習題87行列式的直線式程式289

習題88求和的3帶圖靈機290

習題89模擬RAM指令290

習題810計算22n的RAM程式290

習題811計算g(m,n)的程式291

習題812圖靈機模擬RAM的時間上界291

習題813圖的同構問題291

習題814哈密頓迴路291

習題815P類語言的封閉性292

習題816NP類語言的封閉性292

習題817語言的2O(nk)時間判定算法293

習題818PCONP293

習題819NP≠CONP293

習題820重言布爾表達式294

習題821關係∝p的傳遞性294

習題822L∝pL294

習題823語言的完全性294

習題824L的CONP完全性295

習題825判定重言式的CONP完全性295

習題826析取範式的可滿足性295

習題8272SAT問題的線性時間算法295

習題828整數規劃問題296

習題829劃分問題297

習題830最長簡單迴路問題298

第9章近似算法299

習題91平面圖著色問題的絕對近似算法299

習題92最優程式存儲問題299

習題93樹的最優頂點覆蓋300

習題94頂點覆蓋算法的性能比301

習題95團的常數性能比近似算法302

習題96售貨員問題的常數性能比近似算法302

習題97瓶頸旅行售貨員問題303

習題98最優旅行售貨員迴路不自相交304

習題99集合覆蓋問題的實例304

習題910多機調度問題的近似算法305

習題911LPT算法的最壞情況實例307

習題912多機調度問題的多項式時間近似算法307

算法實現題91旅行售貨員問題的近似算法308

算法實現題92可滿足問題的近似算法310

算法實現題93最大可滿足問題的近似算法311

算法實現題94子集和問題的近似算法312

算法實現題95子集和問題的完全多項式時間近似算法313

算法實現題96實現算法greedySetCover313

算法實現題97裝箱問題的近似算法First Fit317

算法實現題98裝箱問題的近似算法Best Fit319

算法實現題99裝箱問題的近似算法First Fit Decreasing320

算法實現題910裝箱問題的近似算法Best Fit Decreasing321

算法實現題911裝箱問題的近似算法Next Fit321

第10章算法最佳化策略325

習題101算法obst的正確性325

習題102矩陣連乘問題的O(n2)時間算法325

習題103貨物儲運問題的費用330

習題104Garsia算法330

算法實現題101貨物儲運問題333

算法實現題102石子合併問題333

算法實現題103最大運輸費用貨物儲運問題334

算法實現題104五邊形問題336

算法實現題105區間圖最短路問題339

算法實現題106圓弧區間最短路問題340

算法實現題107雙機調度問題340

算法實現題108離線最小值問題348

算法實現題109最近公共祖先問題350

算法實現題1010達爾文晶片問題352

算法實現題1011多柱Hanoi塔問題354

算法實現題1012線性時間Huffman算法357

算法實現題1013單機調度問題358

算法實現題1014最大費用單機調度問題361

算法實現題1015飛機加油問題364

第11章線上算法設計365

習題111線上算法LFU的競爭性365

習題112多讀寫頭磁碟問題的線上算法365

習題113帶權頁調度問題365

算法實現題111最優頁調度問題365

算法實現題112線上LRU頁調度369

算法實現題113k服務問題370

參考文獻375第1章算法引論1習題11實參交換1

習題12方法頭簽名1

習題13數組排序判定1

習題14函式的漸近表達式2

習題15O(1)和O(2)的區別2

習題17按漸近階排列表達式2

習題18算法效率2

習題19硬體效率3

習題110函式漸近階3

習題111n!的階4

習題112平均情況下的計算時間複雜性4

算法實現題11統計數字問題4

算法實現題12字典序問題5

算法實現題13最多約數問題6

算法實現題14金幣陣列問題8

算法實現題15最大間隙問題11第2章遞歸與分治策略14

習題21Hanoi 塔問題的非遞歸算法14

習題227個二分搜尋算法15

習題23改寫二分搜尋算法18

習題24大整數乘法的O(nmlog(3/2))算法19

習題255次n/3位整數的乘法19

習題26矩陣乘法21

習題27多項式乘積21

習題28不動點問題的O(logn)時間算法22

習題29主元素問題的線性時間算法22

習題210無序集主元素問題的線性時間算法22

習題211O(1)空間子數組換位算法23

習題212O(1)空間合併算法25

習題213n段合併排序算法32

習題214自然合併排序算法32

習題215最大值和最小值問題的最優算法35

習題216最大值和次大值問題的最優算法35

習題217整數集合排序35

習題218第k小元素問題的計算時間下界36

習題219非增序快速排序算法37

習題220隨機化算法37

習題221隨機化快速排序算法38

習題222隨機排列算法38

習題223算法qSort中的尾遞歸38

習題224用棧模擬遞歸38

習題225算法select中的元素劃分39

習題226O(nlogn)時間快速排序算法40

習題227最接近中位數的k個數40

習題228X和Y的中位數40

習題229網路開關設計41

習題232帶權中位數問題42

習題234構造Gray碼的分治算法43

習題235網球循環賽日程表44目錄算法設計與分析習題解答（第3版）

算法實現題21輸油管道問題（習題230）49

算法實現題22眾數問題（習題231）50

算法實現題23郵局選址問題（習題232）51

算法實現題24馬的Hamilton週遊路線問題（習題233）51

算法實現題25半數集問題60

算法實現題26半數單集問題62

算法實現題27士兵站隊問題63

算法實現題28有重複元素的排列問題63

算法實現題29排列的字典序問題65

算法實現題210集合劃分問題（一）67

算法實現題211集合劃分問題（二）68

算法實現題212雙色Hanoi塔問題69

算法實現題213標準二維表問題71

算法實現題214整數因子分解問題72

算法實現題215有向直線2中值問題72第3章動態規劃76

習題31最長單調遞增子序列76

習題32最長單調遞增子序列的O(nlogn)算法77

習題37漂亮列印78

習題311整數線性規劃問題79

習題312二維背包問題80

習題314Ackermann函式81

習題317最短行駛路線83

習題319最優旅行路線83

算法實現題31獨立任務最優調度問題（習題33）83

算法實現題32最少硬幣問題（習題34）85

算法實現題33序關係計數問題（習題35）86

算法實現題34多重冪計數問題（習題36）87

算法實現題35編輯距離問題（習題38）87

算法實現題36石子合併問題（習題39）89

算法實現題37數字三角形問題（習題310）91

算法實現題38乘法表問題（習題313）92

算法實現題39租用遊艇問題（習題315）93

算法實現題310汽車加油行駛問題（習題316）95

算法實現題311圈乘運算問題（習題318）96

算法實現題312最少費用購物（習題320）102

算法實現題313最大長方體問題（習題321）104

算法實現題314正則表達式匹配問題（習題322）105

算法實現題315雙調旅行售貨員問題（習題323）110

算法實現題316最大k乘積問題（習題524）111

算法實現題317最小m段和問題113

算法實現題318紅黑樹的紅色內結點問題115第4章貪心算法123

習題42活動安排問題的貪心選擇123

習題43背包問題的貪心選擇性質123

習題44特殊的01背包問題124

習題410程式最優存儲問題124

習題413最優裝載問題的貪心算法125

習題418Fibonacci序列的Huffman編碼125

習題419最優前綴碼的編碼序列125

習題421任務集獨立性問題126

習題422矩陣擬陣126

習題423最小權最大獨立子集擬陣126

習題427整數邊權Prim算法126

習題428最大權最小生成樹127

習題429最短路徑的負邊權127

習題430整數邊權Dijkstra算法127

算法實現題41會場安排問題（習題41）128

算法實現題42最優合併問題（習題45）129

算法實現題43磁帶最優存儲問題（習題46）130

算法實現題44磁碟檔案最優存儲問題（習題47）131

算法實現題45程式存儲問題（習題48）132

算法實現題46最優服務次序問題（習題411）133

算法實現題47多處最優服務次序問題（習題412）134

算法實現題48d森林問題（習題414）135

算法實現題49汽車加油問題（習題416）137

算法實現題410區間覆蓋問題（習題417）138

算法實現題411硬幣找錢問題（習題424）138

算法實現題412刪數問題（習題425）139

算法實現題413數列極差問題（習題426）140

算法實現題414嵌套箱問題（習題431）140

算法實現題415套匯問題（習題432）142

算法實現題416信號增強裝置問題（習題517）143

算法實現題417磁帶最大利用率問題（習題49）144

算法實現題418非單位時間任務安排問題（習題415）145

算法實現題419多元Huffman編碼問題（習題420）147

算法實現題420多元Huffman編碼變形149

算法實現題421區間相交問題151

算法實現題422任務時間表問題151第5章回溯法153

習題5\|1裝載問題改進回溯法（一）153

習題5\|2裝載問題改進回溯法（二）154

習題5\|401背包問題的最優解155

習題5\|5最大團問題的疊代回溯法156

習題5\|7旅行售貨員問題的費用上界157

習題5\|8旅行售貨員問題的上界函式158

算法實現題51子集和問題（習題53）159

算法實現題52最小長度電路板排列問題（習題59）160

算法實現題53最小重量機器設計問題（習題510）163

算法實現題54運動員最佳匹配問題（習題511）164

算法實現題55無分隔設定字典問題（習題512）165

算法實現題56無和集問題（習題513）167

算法實現題57n色方柱問題（習題514）168

算法實現題58整數變換問題（習題515）173

算法實現題59拉丁矩陣問題（習題516）175

算法實現題510排列寶石問題（習題516）176

算法實現題511重複拉丁矩陣問題（習題516）179

算法實現題512羅密歐與朱麗葉的迷宮問題181

算法實現題513工作分配問題（習題518）183

算法實現題514獨立鑽石跳棋問題（習題519）184

算法實現題515智力拚圖問題（習題520）191

算法實現題516布線問題（習題521）198

算法實現題517最佳調度問題（習題522）200

算法實現題518無優先權運算問題（習題523）201

算法實現題519世界名畫陳列館問題（習題525）203

算法實現題520世界名畫陳列館問題（不重複監視）（習題526）207

算法實現題521部落衛隊問題（習題56）209

算法實現題522蟲蝕算式問題211

算法實現題523完備環序列問題214

算法實現題524離散01串問題217

算法實現題525噴漆機器人問題218

算法實現題526n2-1謎問題221第6章分支限界法229

習題6101背包問題的棧式分支限界法229

習題62用最大堆存儲活結點的優先佇列式分支限界法231

習題63團頂點數的上界234

習題64團頂點數改進的上界235

習題65修改解旅行售貨員問題的分支限界法235

習題66解旅行售貨員問題的分支限界法中保存已產生的排列樹237

習題67電路板排列問題的佇列式分支限界法239

算法實現題61最小長度電路板排列問題一（習題68）241

算法實現題62最小長度電路板排列問題二（習題69）244

算法實現題63最小權頂點覆蓋問題（習題610）247

算法實現題64無向圖的最大割問題（習題611）250

算法實現題65最小重量機器設計問題（習題612）253

算法實現題66運動員最佳匹配問題（習題613）256

算法實現題67n後問題（習題615）259

算法實現題68圓排列問題（習題616）260

算法實現題69布線問題（習題617）263

算法實現題610最佳調度問題（習題618）265

算法實現題611無優先權運算問題（習題619）268

算法實現題612世界名畫陳列館問題（習題621）271

算法實現題613騎士征途問題274

算法實現題614推箱子問題275

算法實現題615圖形變換問題281

算法實現題616行列變換問題284

算法實現題617重排n2宮問題285

算法實現題618最長距離問題290第7章機率算法296

習題71模擬常態分配隨機變數296

習題72隨機抽樣算法297

習題73隨機產生m個整數297

習題74集合大小的機率算法298

習題75生日問題299

習題76易驗證問題的拉斯維加斯算法300

習題77用數組模擬有序鍊表300

習題78O(n3/2)舍伍德型排序算法300

習題79n後問題解的存在性301

習題711整數因子分解算法302

習題712非蒙特卡羅算法的例子302

習題713重複3次的蒙特卡羅算法303

習題714集合隨機元素算法304

習題715由蒙特卡羅算法構造拉斯維加斯算法305

習題716產生素數算法306

習題718矩陣方程問題306

算法實現題71模平方根問題（習題710）307

算法實現題72集合相等問題（習題717）309

算法實現題73逆矩陣問題（習題719）309

算法實現題74多項式乘積問題（習題720）310

算法實現題75皇后控制問題311

算法實現題763SAT問題314

算法實現題77戰車問題315

算法實現題78圓排列問題317

算法實現題79騎士控制問題319

算法實現題710騎士對攻問題320第8章NP完全性理論322

習題81RAM和RASP程式322

習題82RAM和RASP程式的複雜性322

習題83計算nn的RAM程式322

習題84沒有MULT和DIV指令的RAM程式324

習題85MULT和DIV指令的計算能力324

習題86RAM和RASP的空間複雜性325

習題87行列式的直線式程式325

習題88求和的3帶圖靈機325

習題89模擬RAM指令325

習題810計算22n的RAM程式325

習題811計算g(m,n)的程式326

習題812圖靈機模擬RAM的時間上界326

習題813圖的同構問題326

習題814哈密頓迴路327

習題815P類語言的封閉性327

習題816NP類語言的封閉性328

習題817語言的2O（nk）時間判定算法328

習題818PCONP329

習題819NP≠CONP329

習題820重言布爾表達式329

習題821關係∝p的傳遞性329

習題822L∝p330

習題823語言的完全性330

習題824的CONP完全性330

習題825判定重言式的CONP完全性331

習題826析取範式的可滿足性331

習題8272SAT問題的線性時間算法331

習題828整數規劃問題332

習題829劃分問題333

習題830最長簡單迴路問題334第9章近似算法336

習題91平面圖著色問題的絕對近似算法336

習題92最優程式存儲問題336

習題94樹的最優頂點覆蓋337

習題95頂點覆蓋算法的性能比339

習題96團的常數性能比近似算法339

習題99售貨員問題的常數性能比近似算法340

習題910瓶頸旅行售貨員問題340

習題911最優旅行售貨員迴路不自相交342

習題914集合覆蓋問題的實例342

習題916多機調度問題的近似算法343

習題917LPT算法的最壞情況實例345

習題918多機調度問題的多項式時間近似算法345

算法實現題91旅行售貨員問題的近似算法（習題99）346

算法實現題92可滿足問題的近似算法（習題920）348

算法實現題93最大可滿足問題的近似算法（習題921）349

算法實現題94子集和問題的近似算法（習題915）351

算法實現題95子集和問題的完全多項式時間近似算法352

算法實現題96實現算法greedySetCover（習題913）352

算法實現題97裝箱問題的近似算法First Fit（習題919）356

算法實現題98裝箱問題的近似算法Best Fit（習題919）358

算法實現題99裝箱問題的近似算法First Fit Decreasing（習題919）360

算法實現題910裝箱問題的近似算法Best Fit Decreasing（習題919）361

算法實現題911裝箱問題的近似算法Next Fit361第10章算法最佳化策略365

習題101算法obst的正確性365

習題102矩陣連乘問題的O(n2)時間算法365

習題106貨物儲運問題的費用371

習題107Garsia算法371

算法實現題101貨物儲運問題（習題103）374

算法實現題102石子合併問題（習題104）374

算法實現題103最大運輸費用貨物儲運問題（習題105）375

算法實現題104五邊形問題377

算法實現題105區間圖最短路問題（習題108）381

算法實現題106圓弧區間最短路問題（習題109）381

算法實現題107雙機調度問題（習題1010）382

算法實現題108離線最小值問題（習題1011）390

算法實現題109最近公共祖先問題（習題1012）393

算法實現題1010達爾文晶片問題395

算法實現題1011多柱Hanoi塔問題397

算法實現題1012線性時間Huffman算法400

算法實現題1013單機調度問題402

算法實現題1014最大費用單機調度問題405

算法實現題1015飛機加油問題408

第11章線上算法設計410

習題111線上算法LFU的競爭性410

習題114多讀寫頭磁碟問題的線上算法410

習題116帶權頁調度問題410

算法實現題111最優頁調度問題（習題112）411

算法實現題112線上LRU頁調度（習題113）414

算法實現題113k服務問題（習題115）416

參考文獻422