本书的内容是对《算法设计与分析》的较深入的扩展，许多在主教材中无法讲述的、较深入的主题通过习题的形式展现出来。为了加强学生灵活运用算法设计策略解决实际问题的能力，本书将主教材中的许多习题改造成算法实现题，要求学生不仅设计出解决具体问题的算法，而且能上机实现。

本书内容丰富，观点新颖，理论联系实际。不仅可用作高等院校计算机科学与技术学科各专业本科生和研究生学习计算机算法设计的辅助教材，而且也适合广大工程技术人员和自学读者学习参考。

本书是清华大学出版社出版的“21世纪大学本科计算机专业系列教材”《算法设计与分析》(主教材)配套的辅助教材，对《算法设计与分析》一书中的习题做了详尽的解答。本书的内容是对《算法设计与分析》的较深入的扩展，许多在主教材中无法讲述的、较深入的主题通过习题的形式展现出来。为了加强学生灵活运用算法设计策略解决实际问题的能力，本书将主教材中的许多习题改造成算法实现题，要求学生不仅设计出解决具体问题的算法，而且能上机实现。作者的教学实践反映出，这类算法实现题的教学效果非常好。作者还结合精品课程建设，进行了教材的立体化开发，包括主教材、辅助教材、实验与设计、电子课件和教学网站建设。

本书内容丰富，观点新颖，理论联系实际。不仅可用作高等院校计算机科学与技术学科各专业本科生和研究生学习计算机算法设计的辅助教材，而且也适合广大工程技术人员和自学读者学习参考。

第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

算法实现题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装载问题改进回溯法1153

习题5-2装载问题改进回溯法2154

习题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19矩阵方程问题306

算法实现题71模平方根问题（习题710）307

算法实现题72素数测试问题（习题717）309

算法实现题73集合相等问题（习题718）309

算法实现题74逆矩阵问题（习题720）310

算法实现题75多项式乘积问题（习题721）311

算法实现题76皇后控制问题311

算法实现题773SAT问题315

算法实现题78战车问题316

算法实现题79圆排列问题318

算法实现题710骑士控制问题319

算法实现题711骑士对攻问题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272SAT问题的线性时间算法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

参考文献410