編輯推薦
本書是《
算法設計與分析(第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
習題11實參交換1
習題12方法頭簽名1
習題13數組排序判定1
習題14函式的漸近表達式2
習題15O(1)和O(2)的區別2
習題16按漸近階排列表達式2
習題17算法效率2
習題18硬體效率2
習題19函式漸近階3
習題110n!的階3
習題111平均情況下的計算時間複雜性3
算法實現題11統計數字鞏厚蜜拜問題4
算法實現題12字典序問題5
算法實現題13最多約數問題6
算法實現題14金幣陣列問題7
算法實現題15最大間隙問題10
第2章遞歸與分治策略12
習題21Hanoi 塔問題的非遞歸算法12
習題227個二分搜尋算法13
習題23改寫二分搜尋算法16
習題24大整數乘法的O(nmlog(3/2))算法16
習題255次n/3位整數的乘法16
習題26矩充阿巴陣乘法18
習題27多項式乘積18
習題28不動點問題的O(logn)時間算法19
習題29主元素問題的線性時間算法19
習題210無序集主元素問題的線性時間算法19目錄算法設計與分析習題解答(第3版)習題211O(1)空間子數組換位算法20
習題212O(1)空間合併算法22
習題213n段合併排序算法28
習題214自然合併排序算法28
習題215最大值和最小值問題的最優算法30
習題216最大值和次大值問題的最優算法31
習題217整數集合排序31
習題218第k小元素問題的計算時間下界31
習題222隨機排列算法33
習題223算法qSort中的尾遞歸33
習題224用棧模擬遞歸34
習題225算法select中的元素劃分34
習題226O(nlogn)時間快速排序算法35
習題227最接近中位數的k個數35
習題228X和Y的中位數35
習題229網路開關設計36
習題231構造Gray碼的分治算法38
習題232網球循環賽日程表39
算法實現題21輸油管道問題43
算法實現題22眾數問題44
算法實現題23郵局選址問題45
算法實現題24馬的Hamilton週遊路線問題45
算法實現題25半數集問題53
算法實現題26半數單集問題54
算法實現題27士兵站隊問題55
算法實現題28有重複元素的排列問題56
算法實現題29排列的字典序問題57
算法實現題210集合劃分問題(一)59
算法實現題211集合劃分問題(二)60
算法實現題212雙色Hanoi塔問題61
算法實現題213標準二維表問題63
算法實現題214整數因子分解問題63
算法實現題215有向直線2中值問題64
第3章動態規劃67
習題31最長單調遞增子序列67
習題32最長單調遞增子序列的O(nlogn)算法68
習題33漂亮列印69
習題34整數線性規劃問題70
習題35二維背包問題70
習題36Ackermann函式71
算法實現題31獨立任務最優調度問題73
算法實現題32最少硬幣問題75
算法實現題33序關係計數問題76
算法實現題34多重冪計數問題76
算法實現題35編輯距離問題77
算法實現題36石子合併問題78
算法實現題37數字三角形問題80
算法實現題38乘法表問題81
算法實現題39租用遊艇問題82
算法實現題310汽車加油行駛問題83
算法實現題311圈乘運算問題84
算法實現題312最少費用購物89
算法實現題313最大長方體問題92
算法實現題314正則表達式匹配問題93
算法實現題315雙調旅行售貨員問題96
算法實現題316最大k乘積問題98
算法實現題317最小m段和問題100
算法實現題318紅黑樹的紅色內結點問題101
第4章貪心算法109
習題41活動安排問題的貪心選擇109
習題42背包問題的貪心選擇性質109
習題43特殊的01背包問題110
習題44程式最優存儲問題110
習題45最優裝載問題的貪心算法110
習題47最優前綴碼的編碼序列111
習題48任務集獨立性問題111
習題49矩陣擬陣111
習題410最小權最大獨立子集擬陣112
習題411整數邊權Prim算法112
習題412最大權最小生成樹112
習題413最短路徑的負邊權113
習題414整數邊權Dijkstra算法113
算法實現題41會場安排問題113
算法實現題42最優合併問題115
算法實現題43磁帶最優存儲問題115
算法實現題44磁碟檔案最優存儲問題116
算法實現題45程式存儲問題117
算法實現題46最優服務次序問題118
算法實現題47多處最優服務次序問題119
算法實現題48d森林問題120
算法實現題49汽車加油問題121
算法實現題410區間覆蓋問題122
算法實現題411硬幣找錢問題123
算法實現題412刪數問題123
算法實現題413數列極差問題124
算法實現題414嵌套箱問題124
算法實現題415套匯問題126
算法實現題416信號增強裝置問題127
算法實現題417磁帶最大利用率問題128
算法實現題418非單位時間任務安排問題129
算法實現題420多元Huffman編碼變形132
算法實現題421區間相交問題134
算法實現題422任務時間表問題134
第5章回溯法136
習題5\|1裝載問題改進回溯法(一)136
習題5\|2裝載問題改進回溯法(二)137
習題5\|301背包問題的最優解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\|101背包問題的棧式分支限界法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
習題71模擬常態分配隨機變數264
習題72隨機抽樣算法265
習題73隨機產生m個整數265
習題74集合大小的機率算法266
習題75生日問題266
習題77用數組模擬有序鍊表268
習題78O(n3/2)舍伍德型排序算法268
習題79n後問題解的存在性268
習題710整數因子分解算法269
習題711非蒙特卡羅算法的例子270
習題712重複3次的蒙特卡羅算法271
習題713集合隨機元素算法271
習題715產生素數算法273
習題716矩陣方程問題273
算法實現題71模平方根問題274
算法實現題72集合相等問題275
算法實現題73逆矩陣問題276
算法實現題74多項式乘積問題277
算法實現題75皇后控制問題277
算法實現題763SAT問題280
算法實現題77戰車問題281
算法實現題78圓排列問題283
算法實現題79騎士控制問題284
算法實現題710騎士對攻問題285
習題81RAM和RASP程式287
習題82RAM和RASP程式的複雜性287
習題83計算nn的RAM程式287
習題84沒有MULT和DIV指令的RAM程式289
習題85MULT和DIV指令的計算能力289
習題86RAM和RASP的空間複雜性289
習題87行列式的直線式程式289
習題88求和的3帶圖靈機290
習題89模擬RAM指令290
習題810計算22n的RAM程式290
習題811計算g(m,n)的程式291
習題812圖靈機模擬RAM的時間上界291
習題813圖的同構問題291
習題815P類語言的封閉性292
習題816NP類語言的封閉性292
習題817語言的2O(nk)時間判定算法293
習題818PCONP293
習題819NP≠CONP293
習題821關係∝p的傳遞性294
習題822L∝pL294
習題823語言的完全性294
習題824L的CONP完全性295
習題825判定重言式的CONP完全性295
習題826析取範式的可滿足性295
習題8272SAT問題的線性時間算法295
習題828整數規劃問題296
習題829劃分問題297
習題830最長簡單迴路問題298
第9章近似算法299
習題91平面圖著色問題的絕對近似算法299
習題92最優程式存儲問題299
習題93樹的最優頂點覆蓋300
習題94頂點覆蓋算法的性能比301
習題95團的常數性能比近似算法302
習題96售貨員問題的常數性能比近似算法302
習題97瓶頸旅行售貨員問題303
習題98最優旅行售貨員迴路不自相交304
習題99集合覆蓋問題的實例304
習題910多機調度問題的近似算法305
習題911LPT算法的最壞情況實例307
習題912多機調度問題的多項式時間近似算法307
算法實現題91旅行售貨員問題的近似算法308
算法實現題92可滿足問題的近似算法310
算法實現題93最大可滿足問題的近似算法311
算法實現題94子集和問題的近似算法312
算法實現題95子集和問題的完全多項式時間近似算法313
算法實現題96實現算法greedySetCover313
算法實現題97裝箱問題的近似算法First Fit317
算法實現題98裝箱問題的近似算法Best Fit319
算法實現題99裝箱問題的近似算法First Fit Decreasing320
算法實現題910裝箱問題的近似算法Best Fit Decreasing321
算法實現題911裝箱問題的近似算法Next Fit321
第10章算法最佳化策略325
習題101算法obst的正確性325
習題102矩陣連乘問題的O(n2)時間算法325
習題103貨物儲運問題的費用330
習題104Garsia算法330
算法實現題101貨物儲運問題333
算法實現題102石子合併問題333
算法實現題103最大運輸費用貨物儲運問題334
算法實現題104五邊形問題336
算法實現題105區間圖最短路問題339
算法實現題106圓弧區間最短路問題340
算法實現題107雙機調度問題340
算法實現題108離線最小值問題348
算法實現題109最近公共祖先問題350
算法實現題1010達爾文晶片問題352
算法實現題1011多柱Hanoi塔問題354
算法實現題1012線性時間Huffman算法357
算法實現題1013單機調度問題358
算法實現題1014最大費用單機調度問題361
算法實現題1015飛機加油問題364
第11章線上算法設計365
習題111線上算法LFU的競爭性365
習題112多讀寫頭磁碟問題的線上算法365
習題113帶權頁調度問題365
算法實現題111最優頁調度問題365
算法實現題112線上LRU頁調度369
算法實現題113k服務問題370
參考文獻375第1章算法引論1習題11實參交換1
習題12方法頭簽名1
習題13數組排序判定1
習題14函式的漸近表達式2
習題15O(1)和O(2)的區別2
習題17按漸近階排列表達式2
習題18算法效率2
習題19硬體效率3
習題110函式漸近階3
習題111n!的階4
習題112平均情況下的計算時間複雜性4
算法實現題11統計數字問題4
算法實現題12字典序問題5
算法實現題13最多約數問題6
算法實現題14金幣陣列問題8
算法實現題15最大間隙問題11第2章遞歸與分治策略14
習題21Hanoi 塔問題的非遞歸算法14
習題227個二分搜尋算法15
習題23改寫二分搜尋算法18
習題24大整數乘法的O(nmlog(3/2))算法19
習題255次n/3位整數的乘法19
習題26矩陣乘法21
習題27多項式乘積21
習題28不動點問題的O(logn)時間算法22
習題29主元素問題的線性時間算法22
習題210無序集主元素問題的線性時間算法22
習題211O(1)空間子數組換位算法23
習題212O(1)空間合併算法25
習題213n段合併排序算法32
習題214自然合併排序算法32
習題215最大值和最小值問題的最優算法35
習題216最大值和次大值問題的最優算法35
習題217整數集合排序35
習題218第k小元素問題的計算時間下界36
習題219非增序快速排序算法37
習題220隨機化算法37
習題221隨機化快速排序算法38
習題222隨機排列算法38
習題223算法qSort中的尾遞歸38
習題224用棧模擬遞歸38
習題225算法select中的元素劃分39
習題226O(nlogn)時間快速排序算法40
習題227最接近中位數的k個數40
習題228X和Y的中位數40
習題229網路開關設計41
習題234構造Gray碼的分治算法43
習題235網球循環賽日程表44目錄算法設計與分析習題解答(第3版)
算法實現題21輸油管道問題(習題230)49
算法實現題22眾數問題(習題231)50
算法實現題23郵局選址問題(習題232)51
算法實現題24馬的Hamilton週遊路線問題(習題233)51
算法實現題25半數集問題60
算法實現題26半數單集問題62
算法實現題27士兵站隊問題63
算法實現題28有重複元素的排列問題63
算法實現題29排列的字典序問題65
算法實現題210集合劃分問題(一)67
算法實現題211集合劃分問題(二)68
算法實現題212雙色Hanoi塔問題69
算法實現題213標準二維表問題71
算法實現題214整數因子分解問題72
算法實現題215有向直線2中值問題72第3章動態規劃76
習題31最長單調遞增子序列76
習題32最長單調遞增子序列的O(nlogn)算法77
習題37漂亮列印78
習題311整數線性規劃問題79
習題312二維背包問題80
習題317最短行駛路線83
習題319最優旅行路線83
算法實現題31獨立任務最優調度問題(習題33)83
算法實現題32最少硬幣問題(習題34)85
算法實現題33序關係計數問題(習題35)86
算法實現題34多重冪計數問題(習題36)87
算法實現題35編輯距離問題(習題38)87
算法實現題36石子合併問題(習題39)89
算法實現題37數字三角形問題(習題310)91
算法實現題38乘法表問題(習題313)92
算法實現題39租用遊艇問題(習題315)93
算法實現題310汽車加油行駛問題(習題316)95
算法實現題311圈乘運算問題(習題318)96
算法實現題312最少費用購物(習題320)102
算法實現題313最大長方體問題(習題321)104
算法實現題314正則表達式匹配問題(習題322)105
算法實現題315雙調旅行售貨員問題(習題323)110
算法實現題316最大k乘積問題(習題524)111
算法實現題317最小m段和問題113
算法實現題318紅黑樹的紅色內結點問題115第4章貪心算法123
習題42活動安排問題的貪心選擇123
習題43背包問題的貪心選擇性質123
習題44特殊的01背包問題124
習題410程式最優存儲問題124
習題413最優裝載問題的貪心算法125
習題418Fibonacci序列的Huffman編碼125
習題419最優前綴碼的編碼序列125
習題421任務集獨立性問題126
習題422矩陣擬陣126
習題423最小權最大獨立子集擬陣126
習題427整數邊權Prim算法126
習題428最大權最小生成樹127
習題429最短路徑的負邊權127
算法實現題41會場安排問題(習題41)128
算法實現題42最優合併問題(習題45)129
算法實現題43磁帶最優存儲問題(習題46)130
算法實現題44磁碟檔案最優存儲問題(習題47)131
算法實現題45程式存儲問題(習題48)132
算法實現題46最優服務次序問題(習題411)133
算法實現題47多處最優服務次序問題(習題412)134
算法實現題48d森林問題(習題414)135
算法實現題49汽車加油問題(習題416)137
算法實現題410區間覆蓋問題(習題417)138
算法實現題411硬幣找錢問題(習題424)138
算法實現題412刪數問題(習題425)139
算法實現題413數列極差問題(習題426)140
算法實現題414嵌套箱問題(習題431)140
算法實現題415套匯問題(習題432)142
算法實現題416信號增強裝置問題(習題517)143
算法實現題417磁帶最大利用率問題(習題49)144
算法實現題418非單位時間任務安排問題(習題415)145
算法實現題419多元Huffman編碼問題(習題420)147
算法實現題420多元Huffman編碼變形149
算法實現題421區間相交問題151
算法實現題422任務時間表問題151第5章回溯法153
習題5\|1裝載問題改進回溯法(一)153
習題5\|2裝載問題改進回溯法(二)154
習題5\|401背包問題的最優解155
習題5\|5最大團問題的疊代回溯法156
習題5\|7旅行售貨員問題的費用上界157
習題5\|8旅行售貨員問題的上界函式158
算法實現題51子集和問題(習題53)159
算法實現題52最小長度電路板排列問題(習題59)160
算法實現題53最小重量機器設計問題(習題510)163
算法實現題54運動員最佳匹配問題(習題511)164
算法實現題55無分隔設定字典問題(習題512)165
算法實現題56無和集問題(習題513)167
算法實現題57n色方柱問題(習題514)168
算法實現題58整數變換問題(習題515)173
算法實現題59拉丁矩陣問題(習題516)175
算法實現題510排列寶石問題(習題516)176
算法實現題511重複拉丁矩陣問題(習題516)179
算法實現題512羅密歐與朱麗葉的迷宮問題181
算法實現題513工作分配問題(習題518)183
算法實現題514獨立鑽石跳棋問題(習題519)184
算法實現題515智力拚圖問題(習題520)191
算法實現題516布線問題(習題521)198
算法實現題517最佳調度問題(習題522)200
算法實現題518無優先權運算問題(習題523)201
算法實現題519世界名畫陳列館問題(習題525)203
算法實現題520世界名畫陳列館問題(不重複監視)(習題526)207
算法實現題521部落衛隊問題(習題56)209
算法實現題522蟲蝕算式問題211
算法實現題523完備環序列問題214
算法實現題524離散01串問題217
算法實現題525噴漆機器人問題218
算法實現題526n2-1謎問題221第6章分支限界法229
習題6101背包問題的棧式分支限界法229
習題62用最大堆存儲活結點的優先佇列式分支限界法231
習題63團頂點數的上界234
習題64團頂點數改進的上界235
習題65修改解旅行售貨員問題的分支限界法235
習題66解旅行售貨員問題的分支限界法中保存已產生的排列樹237
習題67電路板排列問題的佇列式分支限界法239
算法實現題61最小長度電路板排列問題一(習題68)241
算法實現題62最小長度電路板排列問題二(習題69)244
算法實現題63最小權頂點覆蓋問題(習題610)247
算法實現題64無向圖的最大割問題(習題611)250
算法實現題65最小重量機器設計問題(習題612)253
算法實現題66運動員最佳匹配問題(習題613)256
算法實現題67n後問題(習題615)259
算法實現題68圓排列問題(習題616)260
算法實現題69布線問題(習題617)263
算法實現題610最佳調度問題(習題618)265
算法實現題611無優先權運算問題(習題619)268
算法實現題612世界名畫陳列館問題(習題621)271
算法實現題613騎士征途問題274
算法實現題614推箱子問題275
算法實現題615圖形變換問題281
算法實現題616行列變換問題284
算法實現題617重排n2宮問題285
算法實現題618最長距離問題290第7章機率算法296
習題71模擬常態分配隨機變數296
習題72隨機抽樣算法297
習題73隨機產生m個整數297
習題74集合大小的機率算法298
習題75生日問題299
習題76易驗證問題的拉斯維加斯算法300
習題77用數組模擬有序鍊表300
習題78O(n3/2)舍伍德型排序算法300
習題79n後問題解的存在性301
習題711整數因子分解算法302
習題712非蒙特卡羅算法的例子302
習題713重複3次的蒙特卡羅算法303
習題714集合隨機元素算法304
習題715由蒙特卡羅算法構造拉斯維加斯算法305
習題716產生素數算法306
習題718矩陣方程問題306
算法實現題71模平方根問題(習題710)307
算法實現題72集合相等問題(習題717)309
算法實現題73逆矩陣問題(習題719)309
算法實現題74多項式乘積問題(習題720)310
算法實現題75皇后控制問題311
算法實現題763SAT問題314
算法實現題77戰車問題315
算法實現題78圓排列問題317
算法實現題79騎士控制問題319
算法實現題710騎士對攻問題320第8章
NP完全性理論322
習題81RAM和RASP程式322
習題82RAM和RASP程式的複雜性322
習題83計算nn的RAM程式322
習題84沒有MULT和DIV指令的RAM程式324
習題85MULT和DIV指令的計算能力324
習題86RAM和RASP的空間複雜性325
習題87行列式的直線式程式325
習題88求和的3帶圖靈機325
習題89模擬RAM指令325
習題810計算22n的RAM程式325
習題811計算g(m,n)的程式326
習題812圖靈機模擬RAM的時間上界326
習題813圖的同構問題326
習題815P類語言的封閉性327
習題816NP類語言的封閉性328
習題817語言的2O(nk)時間判定算法328
習題818PCONP329
習題819NP≠CONP329
習題821關係∝p的傳遞性329
習題822L∝p330
習題823語言的完全性330
習題824的CONP完全性330
習題825判定重言式的CONP完全性331
習題826析取範式的可滿足性331
習題8272SAT問題的線性時間算法331
習題828整數規劃問題332
習題829劃分問題333
習題830最長簡單迴路問題334第9章近似算法336
習題91平面圖著色問題的絕對近似算法336
習題92最優程式存儲問題336
習題94樹的最優頂點覆蓋337
習題95頂點覆蓋算法的性能比339
習題96團的常數性能比近似算法339
習題99售貨員問題的常數性能比近似算法340
習題910瓶頸旅行售貨員問題340
習題911最優旅行售貨員迴路不自相交342
習題914集合覆蓋問題的實例342
習題916多機調度問題的近似算法343
習題917LPT算法的最壞情況實例345
習題918多機調度問題的多項式時間近似算法345
算法實現題91旅行售貨員問題的近似算法(習題99)346
算法實現題92可滿足問題的近似算法(習題920)348
算法實現題93最大可滿足問題的近似算法(習題921)349
算法實現題94子集和問題的近似算法(習題915)351
算法實現題95子集和問題的完全多項式時間近似算法352
算法實現題96實現算法greedySetCover(習題913)352
算法實現題97裝箱問題的近似算法First Fit(習題919)356
算法實現題98裝箱問題的近似算法Best Fit(習題919)358
算法實現題99裝箱問題的近似算法First Fit Decreasing(習題919)360
算法實現題910裝箱問題的近似算法Best Fit Decreasing(習題919)361
算法實現題911裝箱問題的近似算法Next Fit361第10章算法最佳化策略365
習題101算法obst的正確性365
習題102矩陣連乘問題的O(n2)時間算法365
習題106貨物儲運問題的費用371
習題107Garsia算法371
算法實現題101貨物儲運問題(習題103)374
算法實現題102石子合併問題(習題104)374
算法實現題103最大運輸費用貨物儲運問題(習題105)375
算法實現題104五邊形問題377
算法實現題105區間圖最短路問題(習題108)381
算法實現題106圓弧區間最短路問題(習題109)381
算法實現題107雙機調度問題(習題1010)382
算法實現題108離線最小值問題(習題1011)390
算法實現題109最近公共祖先問題(習題1012)393
算法實現題1010達爾文晶片問題395
算法實現題1011多柱Hanoi塔問題397
算法實現題1012線性時間Huffman算法400
算法實現題1013單機調度問題402
算法實現題1014最大費用單機調度問題405
算法實現題1015飛機加油問題408
第11章線上算法設計410
習題111線上算法LFU的競爭性410
習題114多讀寫頭磁碟問題的線上算法410
習題116帶權頁調度問題410
算法實現題111最優頁調度問題(習題112)411
算法實現題112線上LRU頁調度(習題113)414
算法實現題113k服務問題(習題115)416
參考文獻422
算法實現題44磁碟檔案最優存儲問題(習題47)131
算法實現題45程式存儲問題(習題48)132
算法實現題46最優服務次序問題(習題411)133
算法實現題47多處最優服務次序問題(習題412)134
算法實現題48d森林問題(習題414)135
算法實現題49汽車加油問題(習題416)137
算法實現題410區間覆蓋問題(習題417)138
算法實現題411硬幣找錢問題(習題424)138
算法實現題412刪數問題(習題425)139
算法實現題413數列極差問題(習題426)140
算法實現題414嵌套箱問題(習題431)140
算法實現題415套匯問題(習題432)142
算法實現題416信號增強裝置問題(習題517)143
算法實現題417磁帶最大利用率問題(習題49)144
算法實現題418非單位時間任務安排問題(習題415)145
算法實現題419多元Huffman編碼問題(習題420)147
算法實現題420多元Huffman編碼變形149
算法實現題421區間相交問題151
算法實現題422任務時間表問題151第5章回溯法153
習題5\|1裝載問題改進回溯法(一)153
習題5\|2裝載問題改進回溯法(二)154
習題5\|401背包問題的最優解155
習題5\|5最大團問題的疊代回溯法156
習題5\|7旅行售貨員問題的費用上界157
習題5\|8旅行售貨員問題的上界函式158
算法實現題51子集和問題(習題53)159
算法實現題52最小長度電路板排列問題(習題59)160
算法實現題53最小重量機器設計問題(習題510)163
算法實現題54運動員最佳匹配問題(習題511)164
算法實現題55無分隔設定字典問題(習題512)165
算法實現題56無和集問題(習題513)167
算法實現題57n色方柱問題(習題514)168
算法實現題58整數變換問題(習題515)173
算法實現題59拉丁矩陣問題(習題516)175
算法實現題510排列寶石問題(習題516)176
算法實現題511重複拉丁矩陣問題(習題516)179
算法實現題512羅密歐與朱麗葉的迷宮問題181
算法實現題513工作分配問題(習題518)183
算法實現題514獨立鑽石跳棋問題(習題519)184
算法實現題515智力拚圖問題(習題520)191
算法實現題516布線問題(習題521)198
算法實現題517最佳調度問題(習題522)200
算法實現題518無優先權運算問題(習題523)201
算法實現題519世界名畫陳列館問題(習題525)203
算法實現題520世界名畫陳列館問題(不重複監視)(習題526)207
算法實現題521部落衛隊問題(習題56)209
算法實現題522蟲蝕算式問題211
算法實現題523完備環序列問題214
算法實現題524離散01串問題217
算法實現題525噴漆機器人問題218
算法實現題526n2-1謎問題221第6章分支限界法229
習題6101背包問題的棧式分支限界法229
習題62用最大堆存儲活結點的優先佇列式分支限界法231
習題63團頂點數的上界234
習題64團頂點數改進的上界235
習題65修改解旅行售貨員問題的分支限界法235
習題66解旅行售貨員問題的分支限界法中保存已產生的排列樹237
習題67電路板排列問題的佇列式分支限界法239
算法實現題61最小長度電路板排列問題一(習題68)241
算法實現題62最小長度電路板排列問題二(習題69)244
算法實現題63最小權頂點覆蓋問題(習題610)247
算法實現題64無向圖的最大割問題(習題611)250
算法實現題65最小重量機器設計問題(習題612)253
算法實現題66運動員最佳匹配問題(習題613)256
算法實現題67n後問題(習題615)259
算法實現題68圓排列問題(習題616)260
算法實現題69布線問題(習題617)263
算法實現題610最佳調度問題(習題618)265
算法實現題611無優先權運算問題(習題619)268
算法實現題612世界名畫陳列館問題(習題621)271
算法實現題613騎士征途問題274
算法實現題614推箱子問題275
算法實現題615圖形變換問題281
算法實現題616行列變換問題284
算法實現題617重排n2宮問題285
算法實現題618最長距離問題290第7章機率算法296
習題71模擬常態分配隨機變數296
習題72隨機抽樣算法297
習題73隨機產生m個整數297
習題74集合大小的機率算法298
習題75生日問題299
習題76易驗證問題的拉斯維加斯算法300
習題96團的常數性能比近似算法339
習題99售貨員問題的常數性能比近似算法340
習題910瓶頸旅行售貨員問題340
習題911最優旅行售貨員迴路不自相交342
習題914集合覆蓋問題的實例342
習題916多機調度問題的近似算法343
習題917LPT算法的最壞情況實例345
習題918多機調度問題的多項式時間近似算法345
算法實現題91旅行售貨員問題的近似算法(習題99)346
算法實現題92可滿足問題的近似算法(習題920)348
算法實現題93最大可滿足問題的近似算法(習題921)349
算法實現題94子集和問題的近似算法(習題915)351
算法實現題95子集和問題的完全多項式時間近似算法352
算法實現題96實現算法greedySetCover(習題913)352
算法實現題97裝箱問題的近似算法First Fit(習題919)356
算法實現題98裝箱問題的近似算法Best Fit(習題919)358
算法實現題99裝箱問題的近似算法First Fit Decreasing(習題919)360
算法實現題910裝箱問題的近似算法Best Fit Decreasing(習題919)361
算法實現題911裝箱問題的近似算法Next Fit361第10章算法最佳化策略365
習題101算法obst的正確性365
習題102矩陣連乘問題的O(n2)時間算法365
習題106貨物儲運問題的費用371
習題107Garsia算法371
算法實現題101貨物儲運問題(習題103)374
算法實現題102石子合併問題(習題104)374
算法實現題103最大運輸費用貨物儲運問題(習題105)375
算法實現題104五邊形問題377
算法實現題105區間圖最短路問題(習題108)381
算法實現題106圓弧區間最短路問題(習題109)381
算法實現題107雙機調度問題(習題1010)382
算法實現題108離線最小值問題(習題1011)390
算法實現題109最近公共祖先問題(習題1012)393
算法實現題1010達爾文晶片問題395
算法實現題1011多柱Hanoi塔問題397
算法實現題1012線性時間Huffman算法400
算法實現題1013單機調度問題402
算法實現題1014最大費用單機調度問題405
算法實現題1015飛機加油問題408