第1章 算法引论 1
习题1-1 实参交换 1
习题1-2 方法头签名 1
习题1-3 数组排序判定 1
习题1-4 函数的渐近表达式 2
习题1-5 O(1)和O(2)的区别 2
习题1-7 按渐近阶排列表达式 2
习题1-8 算法效率 2
习题1-9 硬件效率 3
习题1-10 函数渐近阶 3
习题1-11 n!的阶 4
习题1-12 平均情况下的计算时间复杂性 4
算法实现题1-1 统计数字问题 4
算法实现题1-2 字典序问题 5
算法实现题1-3 最多约数问题 6
算法实现题1-4 金币阵列问题 8
算法实现题1-5 最大间隙问题 11
第2章 递归与分治策略 14
习题2-1 Hanoi塔问题的非递归算法 14
习题2-2 7个二分搜索算法 15
习题2-3 改写二分搜索算法 18
习题2-4 大整数乘法的O(nmlog(3/2))算法 19
习题2-5 5次n/3位整数的乘法 19
习题2-6 矩阵乘法 21
习题2-7 多项式乘积 21
习题2-8 不动点问题的O(logn)时间算法 22
习题2-9 主元素问题的线性时间算法 22
习题2-10 无序集主元素问题的线性时间算法 22
习题2-11 O(1)空间子数组换位算法 23
习题2-12 O(1)空间合并算法 25
习题2-13 ?段合并排序算法 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-26 O(nlogn)时间快速排序算法 40
习题2 27 最接近中位数的k个数 40
习题2-28 X和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 马的HamiIton周游路线问题(习题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-14 Ackermann函数 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 最小n段和问题 113
算法实现题3-18 红黑树的红色内结点问题 115
第4章 贪心算法 123
习题4-2 活动安排问题的贪心选择 123
习题4-3 背包问题的贪心选择性质 123
习题4-4 特殊的0-1背包问题 124
习题4-10 程序最优存储问题 124
习题4-13 最优装载问题的贪心算法 125
习题4-18 Fibonacci序列的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-8 d森林问题(习题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-4 0-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-7 n色方柱问题(习题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-26 n2-1谜问题 221
第6章 分支限界法 229
习题6-1 0-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-7 n后问题(习题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-8 O(n3/2)舍伍德型排序算法 300
习题7-9 n后问题解的存在性 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-6 3-SAT问题 314
算法实现题7-7 战车问题 315
算法实现题7-8 圆排列问题 317
算法实现题7-9 骑士控制问题 319
算法实现题7-10 骑士对攻问题 320
第8章 NP完全性理论 322
习题8-1 RAM和RASP程序 322
习题8-2 RAM和RASP程序的复杂性 322
习题8-3 计算nn的RAM程序 322
习题8-4 没有MULT和DIV指令的RAM程序 324
习题8-5 MULT和DIV指令的计算能力 324
习题8-6 RAM和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-15 P类语言的封闭性 327
习题8-16 NP类语言的封闭性 328
习题8-17 语言的2o(nk)时间判定算法 328
习题8-18 P?CO-NP 329
习题8-19 NP≠CO-NP 329
习题8-20 重言布尔表达式 329
习题8-21 关系?p的传递性 329
习题8-22 L?p? 330
习题8-23 语言的完全性 330
习题8-24 ?的CO-NP完全性 330
习题8-25 判定重言式的CO-NP完全性 331
习题8-26 析取范式的可满足性 331
习题8-27 2-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-17 LPT算法的最坏情况实例 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 Fit 361
第10章 算法优化策略 365
习题10-1 算法obst的正确性 365
习题10-2 矩阵连乘问题的O(n2)时间算法 365
习题10-6 货物储运问题的费用 371
习题10-7 Garsia算法 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-3 k服务问题(习题11-5) 416