算法設計與分析習題解答(第3版)

算法設計與分析習題解答(第3版)

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

基本介紹

  • 中文名:算法設計與分析習題解答
  • 作者:王曉東
  • 出版社清華大學出版社
  • 出版時間:2014年2月1日
  • 頁數:374 頁
  • 定價:39.00
  • 開本:16 開
  • 裝幀:平裝
  • ISBN:9787302348634
編輯推薦,內容簡介,作者簡介,圖書目錄,

編輯推薦

本書是《算法設計與分析(第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

圖書目錄

第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

相關詞條

熱門詞條

聯絡我們