没有合适的资源?快使用搜索试试~ 我知道了~
首页《算法导论》课后习题解答
"这是一份关于《算法导论》第二版的课后习题答案,由Philip Bille编撰。这份文档包含了对书中部分练习题的解答,但作者不对内容的准确性负责,可能存在错误。建议读者首先尝试自己解决问题,仅将此文档作为最后的参考或校验工具。文档处于持续更新状态,不定期会有改进。" 在《算法导论》这本书中,习题解答覆盖了各种算法和数据结构的基础知识,是提升编程技能的重要资源。例如,文档中提到了1.2-2这道题目,它涉及到了比较插入排序和归并排序的效率。题目指出当8n^2 < 64n log n时,插入排序比归并排序更优。通过计算得出,当n小于8 log n,即2n/8 < n时,这个条件成立。这个不等式在2 <= n <= 43的范围内成立。因此,为了优化运行时间,可以修改归并排序的实现,对于输入大小为43或更小的情况,改用插入排序。 1-1题则可能涉及到时间单位的转换,如将秒、分钟、小时等单位相互转换,这是计算机科学中常见的基础计算问题,特别是在处理时间相关的算法和系统设计时。 这些习题答案涵盖了算法分析的关键概念,如时间复杂度、排序算法的效率比较以及基本的数学推理。通过深入理解和解决这些问题,读者可以深化对算法的理解,提高解决问题的能力。同时,文档鼓励读者独立思考,先尝试自己解题,再用提供的答案进行核对,这是一种有效的学习方法。 请注意,由于原始信息中部分内容缺失,无法提供完整的习题解答内容。不过,从给出的部分来看,这份资料对于正在学习《算法导论》的人来说,是一个宝贵的辅助工具,有助于他们在实践中巩固理论知识。
资源详情
资源推荐
Initialization: Before the first iteration of the while the only change of the max-heap is that A[i]
is increased an may therefore violate the max-heap property.
Maintenance: Immediately before the iteration i and the child that violated the max-heap prop-
erty has been exchanged thus restoring the max-heap property between these. This can only
destroy the max-heap property between i and the parent of i.
Termination: The termination condition of the while states that at the end of the iteration the
max-heap property between i and its parent is restored or the i is the root of the heap.
We see by the loop invariant that the heap property is restored at end of the iteration.
6.5 − 7
Algorithm 5 HEAP-DELETE(A, i)
Input: A max-heap A and integers i.
Output: The heap A with the element a position i deleted.
A[i] ↔A[heap-size[A]]
heap-size[A] ←heap-size[A] − 1
key ←A[i]
if key 6 A[PARENT(i)] then
MAX-HEAPIFY(A, i)
else
while i > 1 and A[PARENT(i)] < key do
A[i] ↔A[PARENT(i)]
i ←PARENT(i)
end while
end if
6.5 − 8
Given k sorted lists with a total of n elements show how to merge them in O(n lg k) time. Insert
all k elements a position 1 from each list into a heap. Use EXTRACT-MAX to obtain the first element
of the merged list. Insert element at position 2 from the list where the largest element originally
came from into the heap. Continuing in this fashion yields the desired algorithm. Clearly the
running time is O(n lg k).
6 − 2
a. A d-ary heap can be implemented using a dimensional array as follows. The root is kept in
A[1], its d children are kept in order in A[2] through A[d+1] and so on. The procedures to map a
node with index i to its parent and its jth child are given by:
D-ARY-PARENT(i)
return b(i − 2)/d + 1c
D-ARY-CHILD(i, j)
return d(i − 1) + j + 1
b. Since each node has d children the height of the tree is Θ(log
d
n).
c. The HEAP-EXTRACT-MAX algorithm given in the text works fine for d-ary heaps; the problem
is MAX-HEAPIFY. Here we need to compare the argument node to all its children. This takes
Θ(d log
d
n) and dominates the overall time spent by HEAP-EXTRACT-MAX.
9
d. The MAX-HEAP-INSERT given in the text works fine as well. The worst-case running time is
the height of the heap, that is Θ(log
d
n).
e. The HEAP-INCREASE-KEY algorithm given in the text works fine.
10
7.1 − 2
When all the elements in A are the same, notice that the comparison in line 4 of PARTITION is
always satified and i therefore is incremented in each iteration. Since initially i ←p − 1 and i + 1
is returned the returned value is r − 1.
To make PARTITION return (p + r)/2 when all elements are the same, simply modify the algo-
rithm to check for this case explicitly.
7.1 − 3
The running time of PARTITION is Θ(n) since each iteration of the for loop involves a constant
number of operations and there is Θ(n) iterations in total.
7.1 − 4
To make QUICKSORT sort in nonincreasing order replace the 6 comparison in PARTITION line 4
with >.
7.2 − 2
If the elements in A are the same, then by exercise 7.1 − 2 the returned element from each call
to PARTITION(A, p, r) is r − 1 thus yielding the worst-case partitioning. The total running time is
easily seen to be Θ(n
2
).
7.2 − 3
If the elements in A are distinct and sorted in decreasing order then, as in the previous exercise,
we have worst-case partitioning. The running time is again Θ(n
2
).
7 − 4
a. Clearly, the QUICKSORT’ does exactly the same as the original QUICKSORT and therefore works
correctly.
b. Worst-case partitioning can cause the stack depth of QUICKSORT’ to be Θ(n).
c. If we recursively call QUICKSORT’ on the smallest subarray returned by PARTITION we will
avoid the problem and retain a O(lg n) bound on the stack depth.
11
剩余50页未读,继续阅读
nisxiya
- 粉丝: 26
- 资源: 18
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 最优条件下三次B样条小波边缘检测算子研究
- 深入解析:wav文件格式结构
- JIRA系统配置指南:代理与SSL设置
- 入门必备:电阻电容识别全解析
- U盘制作启动盘:详细教程解决无光驱装系统难题
- Eclipse快捷键大全:提升开发效率的必备秘籍
- C++ Primer Plus中文版:深入学习C++编程必备
- Eclipse常用快捷键汇总与操作指南
- JavaScript作用域解析与面向对象基础
- 软通动力Java笔试题解析
- 自定义标签配置与使用指南
- Android Intent深度解析:组件通信与广播机制
- 增强MyEclipse代码提示功能设置教程
- x86下VMware环境中Openwrt编译与LuCI集成指南
- S3C2440A嵌入式终端电源管理系统设计探讨
- Intel DTCP-IP技术在数字家庭中的内容保护
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功