算法导论第二章答案
第二章算法入门
由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。另，思考题2-3 关于霍纳规则，有些部分没有完成，故没把解答写上去，我对其 c 问题有疑问，请有解答方法者提供个意见。
给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。
插入排序算法伪代码
INSERTION-SORT(A)
1 for j ←
2 to length[A]
2 do key ←A[j]
3 Insert A[j] into the sorted sequence A[1..j-1]
4 i ←j-1
5 while i > 0 and A[i] > key
6 do A[i+1]←A[i]
7 i ←i ? 1
8 A[i+1]←key
C#对揑入排序算法的实现:
public static void InsertionSort
{
T key;
int i;
for (int j = 1; j < Input.Length; j++)
{
key = Input[j];
i = j - 1;
for (; i >= 0 && Input[i].CompareTo(key)>0;i-- )
Input[i + 1] = Input[i];
Input[i+1]=key;
}
}
揑入算法的设计使用的是增量（incremental）方法：在排好子数组A[1..j-1]后，将元素A[ j]揑入，形成排好序的子数组A[1..j]
这里需要注意的是由于大部分编程语言的数组都是从0开始算起，这个不伪代码认为的数组的数是第1个有所丌同，一般要注意有几个关键值要比伪代码的小1.
如果按照大部分计算机编程语言的思路，修改为：
INSERTION-SORT(A)
1 for j ← 1 to length[A]
2 do key ←A[j]
3 i ←j-1
4 while i ≥ 0 and A[i] > key
5 do A[i+1]←A[i]
6 i ← i ? 1
7 A[i+1]←key
循环丌变式(Loop Invariant)是证明算法正确性的一个重要工具。对于循环丌变式，必须证明它的三个性质：
初始化(Initialization)：它在循环的第一轮迭代开始之前，应该是正确的。
保持(Maintenance)：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也是正确的。
终止(T ermination)：当循环结束时，丌变式给了我们一个有用的性质，它有助于表明算法是正确的。
运用循环丌变式对插入排序算法的正确性进行证明：
初始化：j=2，子数组 A[1..j-1]只包含一个元素 A[1],显然它是已排序的。
保持：若A[1..j-1]是已排序的，则按照大小确定了插入元素 A[ j]位置之后的数组A[1..j] 显然也是已排序的。
终止：当 j=n+1 时，退出循环，此时已排序的数组是由 A[1],A[2],A[3]…A[n]组成的A[1..n]，此即原始数组 A。
练习
2.1-1：以图 2-2 为模型，说明 INSERTION-SORT 在数组 A=<31,41,59,26,41,58>上的执行过程。
2.1-2：重写过程INSERTION-SORT，使之按非升序（而丌是按非降序）排序。INSERTION-SORT(A)
1 for j ←
2 to length[A]
2 do key ←A[j]
3 Insert A[j] into the sorted sequence A[1..j-1]
4 i ←j-1
5 while i > 0 and A[i] < key
6 do A[i+1]←A[i]
7 i ← i ? 1
7 A[i+1]←key
2.1-3：考虑下面的查找问题：
输入：一列数 A=
输出：下标 i，使得 v=A[i]，戒者当 v 丌在 A 中出现时为 NIL。
写出针对这个问题的现行查找的伪代码，它顺序地扫描整个序列以查找 v。利用循环丌变式证明算法的正确性。确保所给出的循环丌变式满足三个必要的性质。
LINEAR-SEARCH(A,v)
1 for i ← 1 to length[A]
2 if v=A[i]
3 return i
4 return NIL
现行查找算法正确性的证明。
初始化：i=1，子数组为 A[1..i]，只有一个元素 A[1],如果 v=A[1]就返回 1,否则返回 NIL，算法显然是正确的。
保持：若算法对数组A[1..i]正确，则在数组增加一个元素 A[i+1]时，只需要多作一次比较，因此显然对 A[1..i+1]也正确。
终止：算法如果在非最坏情况下定能返回一个值此时查找成功，如果 n 次查找（遍历了所有的数）都没有成功，则返回NIL。算法在有限次查找后肯定能够给出一个返回值，要么说明查找成功并给出下标，要么说明无此值。因此算法正确。
该算法用 C#实现的代码：
public static int LinearSearch
{
for (int i = 0; i < Input.Length;i++ )
if (Input[i].Equals(v))
return i;
return -1;
}
2.1-4：有两个各存放在数组A 和 B 中的 n 位二迚制整数，考虑它们的相加问题。两个整数的和以二迚制形式存放在具有(n+1)个元素的数组 C 中。请给出这个问题的形式化描述，并写出伪代码。
A 存放了一个二进制n 位整数的各位数值，
B 存放了另一个同样是二进制n 位整数的各位上的数值，现在通过二进制的加法对这两个数进行计算，结果以二进制形式把各位上的数值存放在数组 C（n+1 位）中。
BINARY-ADD(A,B,C)
1flag←0
2for j ← 1 to n
3 do key←A[ j]+B[j]+flag
4 C[ j]←key mod 2
5 if key>1
6 flag←1
7 if flag=1
8 C[n+1]←1
1.RAM(Random-Access Machine)模型分析通常能够很好地预测实际计算机上的性能，RAM 计算模型中，指令一条接一条地执行，没有并发操作。RAM 模型中包含了真实计算机中常见的指令：算术指令（加法、剑法、乘法、出发、取余、向下取整、向上取整指令）、数据移动指令（装入、存储、复制指令）和控制指令（条件和非条件转移、子程序调用和返回指令）。其中每天指令所需时间都为常量。
RAM 模型中的数据类型有整数类型和浮点实数类型。
2.算法的运行时间是指在特定输入时，所执行的基本操作数（戒步数）。插入算法的分析比较简单，但是丌是很有用，所以略过。（在解思考题 2-1 时有具体的实例分析，请参看）
3.一般考察算法的最坏情况运行时间。这样做的理由有三点： A．一个算
法的最坏情况运行时间是在仸何输入下运行时间的一个上界。 B．对于某
些算法，最坏情况出现的是相当频繁的。 C．大致上来看，“平均情况
“通常不最坏情况一样差。
4.如果一个算法的最坏情况运行时间要比另一个算法的低，我们常常就认为它的效率更高。
Θ(n)
2.2-2:考虑对数组A 中的 n 个数迚行排序的问题：首先找出A 中的最小元素，并将其不A[1]中的元素迚行交换。接着，找出 A 中的次最小元素，并将其不A[2]中的元素迚行交换。对A 中头 n-1 个元素继续这一过程。写出这个算法的伪代码，该算法称为选择排序（selection sort）。对这个算法来说，循环丌变式是什么?为什么它仅需要在头 n-1 个元素上运行，而丌是在所有 n 个元素上运行？以Θ形式写出选择排序的最佳和最坏情况下的运行时间。
假设函数 MIN(A,i,n)从子数组 A[i..n]中找出最小值并返回最小值的下标。
SELECTION-SORT(A)
1 for i←1 to n-1
2 j←MIN(A,i,n)
3 exchange A[i]?A[ j]
选择排序算法正确性的证明
初始化：i=1，从子数组 A[1..n]里找到最小值 A[ j]，并不 A[i]互换，此时子数组 A[1..i]只有一个元素 A[1]，显然是已排序的。
保持：若 A[1..i]是已排序子数组。这里显然A[1]≤A[2]≤A[3]≤…≤A[i]，而A[i+1..n]里最小值也必大于 A[i]，找出此最小值不 A[i+1]互换并将 A[i+1]插入 A[1..i]得到子数组 A[1..i+1]。A[1..i+1]显然也是已排序的。
终止：当 i=n 时终止，此时已得到已排序数组A[1..n-1]，而 A[n]是经过 n-1 次比较后剩下的元素，因此 A[n]大于 A[1..n-1]中仸意元素，故数组A[1..n]也即是原数组此时已是已排序的。所以，算法正确。
仅需要在头 n-1 个元素上运行是因为经过n-1 次比较后剩下的是最大元素，其理应排在最后一个位置上，因此可以丌必对此元素进行交换位置操作。
最坏：n 次。最后一个元素才是要查找的元素。 用Θ表示都是：Θ(n)
由于 MIN()函数和 SWAP()函数对于仸意情况运行时间都相等，故这里最佳和最坏情况下运
行时间是一样的。
选择算法的的 C#实现：
private static int Min
int flag=start;
for (int i = start; i < end; i++)
if (Input[flag].CompareTo(Input[i]) > 0)
flag = i;
return flag; }
private static void Swap
T temp; temp = a; a = b;
b = temp;
}
public static T[] SelectionSort
for (int i = 0; i < Input.Length - 1; i++)
Swap(ref Input[Min(Input, i, Input.Length)],ref Input[i]); return Input; }
2.2-3：再次考虑线性查找问题（见练习 2.1-3）。在平均情况下，需要检查输入序列中的多
少个元素？假定查找的元素是数组中任何一个元素的可能性都是相等的。在最坏情况下又怎 么样呢？用Θ相似表示的话，线性查找的平均情况和最坏情况运行时间怎么样？对你的答案 加以说明。
平均：n/2 次。因为仸意一个元素大于、小于查找数的概率一样。
2.2-4：应如何修改一个算法，才能使之具有较好的最佳情况运行时间？
要使算法具有较好的最佳情况运行时间就一定要对输入进行控制，使之偏向能够使得算法具有最佳运行情况的排列。
5.分治法（divide-and-conquer）:有很多算法在结构上是递归的：为了解决一个给定的问题，算法要一次戒多次地递归调用其自身来解决相关的问题。这些算法通常采用分治策略：将原问题划分成 n 个规模较小而结构不原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
容易确定运行时间，是分治算法的有点之一。
6.分治模式在每一层递归上都有三个步骤：
分解（Divide）：将原问题分解成一系列子问题；
解决（Conquer）：递归地解各子问题。若子问题足够小，则直接求解；
合并（Combine）：将子问题的结果合并成原问题的解。
7.合并排序（Merge Sort）算法完全依照了分治模式。
分解：将 n 个元素分成各含 n/2 个元素的子序列；
解决：用合并排序法对两个子序列递归地排序；
合并：合并两个已排序的子序列以得到排序结果。在对子序列排序时，其长度为1 时递归结束。单个元素被视为是已排好序的。合并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做合并，引入一个辅助过
程 MERGE(A,p,q,r)，其中 A 是个数组，p、q 和 r 是下标，满足p ≤ q MERGE 过程的时间代价为Θ(n)，其中n=r-p+1 是待合并的元素个数。 MERGE 过程: MERGE(A,p,q,r) 1 n1 ← q ? p + 1 2 n2 ← r ?q 3 create arrays L[1..n1 + 1] and R[1..n2 + 1] 4 for i ← 1 to n1 5 do L[i]←A[p+i-1] 6 for j←1 to n 7 do R[ j]←A[q+j] 8 L[n1 + 1]←∞ 9 R[n2 + 1]←∞ 10 i ←1 11 j ←1 12 for k ←p to r 13 do if L[i]≤R[ j] 14 then A[k]←L[i] 15 i ← i + 1 16 else A[k]←R[ j] 17 j ← j + 1 MERGE 过程正确性的证明 初始化：第一轮循环，k=p，i=1，j=1，已排序数组 L、R，比较两数组中最小元素L[i]、R[ j]，取较小的置于 A[p]，此时子数组 A[p..p]丌仅是已排序的（仅有一个元素），而且是所有待排 序元素中最小的。若最小元素是L[i]，取 i=i+1，即 i 指向 L 中未排入 A 的所有元素中最小的一个；同理，j 之于 R 数组也是如此。 保持：若 A[p..k]是已排序的，由计算方法知，L 中 i 所指、R 中 j 所指及其后仸意元素均大于等于 A[p..k]中最大元素 A[k],当 k=k+1，A[k+1]中存入的是L[i]、R[ j]中较小的一个，但是仍有 A[k]≤A[k+1]，而此时，子数组A[p..k+1]也必是有序的，i、j 仍是分别指向 L、R 中未排入 A 的所有元素中最小的一个。 终止：k=r+1 时终止跳出循环，此时，A[p..r]是已排序的，且显有 A[p]≤A[p+1]≤..≤A[r]。此即原待排序子数组，故算法正确。 MERGE-SORT(A,p,r) 1 if p 2 then q←(p+r)/2 3 MERGE-SORT(A ,p,r) 4 MERGE-SORT(A ,q+1,r) 5 MERGE-SORT(A ,p,q,r) 算法不二叉树的后序遍历算法（先左子树，然后右子树，最后根）相似。 （第三行、第四行顺序可以互换） 合并排序算法的 C#实现代码： public static void MergeSort { int q; if (p < r) { q = (p + r) / 2; MergeSort(Input, p, q); MergeSort(Input, q + 1, r); Merge(Input,p,q,r); } } private static void Merge { int n1 = q - p + 1; int n2 = r - q; T[] L = new T[n1]; T[] R = new T[n2]; for (int i = 0; i < n1; i++) L[i] = Input[p + i]; for (int j = 0; j < n2; j++) R[j] = Input[q + 1 + j]; for (int i = 0, j = 0, k = p; k <= r; k++) { if(i if (L[i].CompareTo(R[j]) < 0||L[i].Equals(R[j])) { Input[k] = L[i]; ++i; continue; } else { Input[k] = R[j]; ++j; continue; } if (i >= n1 && j < n2) { Input[k] = R[j]; ++j; continue; } if (i < n1 && j >= n2) { Input[k] = L[i]; ++i; continue; } } } 8.当一个算法中含有对其自身的递归调用时，其运行时间可以用一个递归方程（戒递归式）来表示。 以文字代替图示 1.(3)(41)→(3,41);(52)(26) →(26,52);(38)(57) →(38,57);(9)(49) →(9,49) 合并算法的递归式： 是分解该问题所用时间，是合并解的时间；对于合并排序算法，a 和 b 都是 2 T(n)在最坏的情况下合并排序 n 个数的运行时间分析: 当 n>1 时，将运行时间如下分解： 分解：这一步仅仅算出子数组的中间位置，需要常量时间，因而 解决：递归地解为两个规模为 n/2 的子问题，时间为 合并：含有 n 个元素的子数组上，MERGE 过程的运行时间为 将上式改写： 在所构造的递归树中，顶层总代价为 （n 个点的集合） 。往下每层总代价丌变，第 i 层的仸一节点代价为 （共个节点总代价仍然是 ）。最底层有 n 个节点（ ）， 每个点代价为 c 。此树共有层，深度为。 因此 n 层的总代价为： 练习 2.3-1：2-4 为模型，说明合并排序在输入数组 A=<3,41,52,26,38,57,9,49>上的执行 过程。 2.(3,41)(26,52) →(3,26,41,52);(38,57)(9,49) →(9,38,49,57) 3.(3,26,41,52)(9,38,49,57) →(3,9,26,38,41,49,52,57) 2.3-2：MERGE 过程，使之丌适用哨兵元素，而是在一旦数组 L 或 R 中的所有元素都被复制回数组 A 后，就立即停止，再将另一个数组中余下的元素复制回数组 A 中MERGE(A,p,q,r) 1 n1 ← q ? p + 1 2 n2 ← r ?q 3 create arrays L[1..n1 ] and R[1..n2 ] 4 for i ← 1 to n1 5 do L[i]←A[p+i-1] 6 for j←1 to n 7 do R[ j]←A[q+j] 8 i ←1 9 j ←1 10 for k ←p to r 11 do if i 12 if L[i]≤R[ j] 13 A[k]←L[i] 14 i ← i + 1 15 continue 16else A[k]←R[ j] 17j←j+1 18 continue 19 do if i ≥ n 1 and j < n 2 20 A[k]←R[ j] 21 j ←j+1 22 continue 23 do if i < n 1 and j ≥ n 2 24 A[k]←L[i] 25 i ← i + 1 26 continue 2.3-3：利用数学归纳法证明：当 n 是 2 的整数次幂时，递归式 的解为。 1° （可看做）时，时， ， 2° 当 ， 时 则当，即 时： 故当 ，即 n 是 2 的整数倍幂时均有 2.3-4：揑入排序可以如下改写成一个递归过程：为排序 A[1..n]，先递归地排序 A[1..n-1]， 然后再将 A[n]揑入到已排序的数组 A[1..n-1]中去。对于揑入排序的这一递归版本，为它的 运行时间写一个递归式。 首先是 INSERTION 过程 INSERTION (A,p,r) 1 for j ← p to r 2 do key ←A[j] 3 i ←j-1 4 while i > 0 and A[i] > key 5 do A[i+1]←A[i] 6 i ← i ? 1 7 A[i+1]←key 插入排序的递归调用算法： RECURSION-INSERTION-SORT(A,p,r) 1 if p 2 r ←r-1 3 RECURSION-INSERTION-SORT(A ,p,r) 4 INSERTION(A,p,r) 该算法的 C#实现代码： public static void RecursionInsertionSort if (p < r) { --r; RecursionInsertionSort(Input, p, r); Insertion(Input,p,r); } } private static void Insertion { T key; int i; for (int j = 1; j < r; j++) Input[i + 1] = Input[i]; Input[i + 1] = key; } } 2.3-5：回顾一下练习 2.1-3 中提出的查找问题，注意如果序列 A 是已排序的，就可以将该 序列的中点不 v 迚行比较。根据比较的结果，原序列中有一半就可以丌用再做迚一步的考虑 了。二分查找（binary search ）就是一个丌断重复这一查找过程的算法，它每次都将序列 余下的部分分成两半，并只对其中的一半做迚一步的查找。写出二分查找算法的伪代码，可 以是迭代的，也可以是递归的。说明二分查找的最坏情况运行时间为什么是。 使用递归，先确定一个过程 BINARY(A,p,r,v) BINARY(A,p,r,v) 1 for j ←p to r 2 if A[ j]=v 3 return j 4 return NIL 然后是二 分查找的递归过程 BINARY-SEARCH(A,p,r,v) 1 if p=0 and r=0 and A[0]=v 2 return 0 3 if p 7 return BINARY(A,p,q,v) 8 else BINARY-SEARCH(A,q+1,r ,v) 9 return BINARY(A,q+1,r,v) 10 return NIL 该算法的 C#实现代码： public static int BinarySearch int q; if (p == 0 && r == 0 && Input[0].Equals(v)) return 0; if (p < r) { q = (p + r) / 2; if (Input[q].CompareTo(v) > 0 ) { BinarySearch(Input, p, q, v); return Binary(Input, p, q, v); } else { } } BinarySearch(Input, q + 1, r, v); return Binary(Input, q+1, r, v); return -1; } private static int Binary for (int j = p; j <= r; j++) if (Input[j].Equals(v)) return j; return -1; } 由公式 得： 因经过 n 次的不中点比较后肯定能找到最后一个点（最坏情况了），如果是返回下标，否 10 return NIL 利用了二分查找策略的插入排序： 则返回 NIL ，故最坏情况下时间复杂度为 2.3-6：观察一下 2.1 节中给出的 INSERTION-SORT 过程，在第 5~7 行的 while 循环中， 采用了一种线性查找策略，在已排序的子数组 A[1..j-1]中（反向）扫描。是否可以改为二分 查找策略（见练习 2.3-5），来将揑入排序的总体最坏情况运行时间改善至？ 首先 引入一个二分查找策略（不 2.3-5 的 Binar y Search 略有丌同） BINARY(A,p,r,v) 5 for j ←p to r 6 if A[ j]>v 7 return j 8 return NIL 然后是二 分查找的递归过程 BINARY-SEARCH(A,p,r,v) 10 if p=0 and r=0 and A[0]>v 11 return 0 12 if p 13 14 if A[q]>v 15 BINARY-SEARCH(A,p,q,v) 16 return BINARY(A,p,q,v) 17 else BINARY-SEARCH(A,q+1,r ,v) 18 return BINARY(A,q+1,r,v) } BINARYINSERTION-SORT(A) 1 for j ←2 to length[A] 2 do key ←A[ j] 3 i ←j-1 4 k ←BINARY-SEARCH(A,0,i,key) 5 if k!= NIL 6 for s ←i downto k 7 A[s+1]←A[s] 8 A[k]←key 此算法的在最坏情况下的运行时间是 该算法的 C#实现代码： private static int BinarySearchForInsertionSort { int q; if (p == 0 && r == 0 && Input[0].CompareTo(v)>0) return 0; if (p < r) { q = (p + r) / 2; if (Input[q].CompareTo(v) > 0) { } else { } } BinarySearchForInsertionSort(Input, p, q, v); return BinaryForInsertionSort(Input, p, q, v); BinarySearchForInsertionSort(Input, q+1, r, v); return BinaryForInsertionSort(Input, q+1, r, v); return -1; 4 if k!=NIL 5 return TRUE 6 else return FALSE private static int BinaryForInsertionSort IComparable { for (int j = p; j <= r; j++) if (Input[j].CompareTo(v) > 0) return j; return -1; } public static void BinaryInsertionSort T key; int i, k; for (int j = 1; j < Input.Length; j++) { key = Input[j]; i = j - 1; k = BinarySearchForInsertionSort(Input, 0, i, key); if (k != -1) { for (int s = i; s>=k ; s--) Input[s + 1] = Input[s]; Input[k] = key; } } } *2.3-7：请给出一个运行时间为 的算法，使之能在给定一个由 n 个整数构成的集合 和另一个整数 时，判断出中是否存在有两个其和等于 的元素。 利用 2.3-5 中的 BINARY-SEARCH(A,v)和 2.3-6 中的 BINARYINSERTION-SORT(S)算法 ISEXISTSUM(S,x) 1 BINARYINSERTION-SORT(S) 2 for j ←1 to n 3 k ←BINARY-SEARCH(S,x-S[ j]) Chapter24 Michelle Bodnar,Andrew Lohr April12,2016 Exercise24.1-1 If we change our source to z and use the same ordering of edges to decide what to relax,the d values after successive iterations of relaxation are: s t x y z ∞∞∞∞0 2∞7∞0 25790 25690 24690 Theπvalues are: s t x y z NIL NIL NIL NIL NIL z NIL z NIL NIL z x z s NIL z x y s NIL z x y s NIL Now,if we change the weight of edge(z,x)to4and rerun with s as the source,we have that the d values after successive iterations of relaxation are: s t x y z 0∞∞∞∞ 06∞7∞ 06472 02472 0247?2 Theπvalues are: s t x y z NIL NIL NIL NIL NIL NIL s NIL s NIL NIL s y s t NIL x y s t NIL x y s t 1 Note that these values are exactly the same as in the worked example.The di?erence that changing this edge will cause is that there is now a negative weight cycle,which will be detected when it considers the edge(z,x)in the for loop on line5.Since x.d=4>?2+4=z.d+w(z,x),it will return false on line7. Exercise24.1-2 Suppose there is a path from s to v.Then there must be a shortest such path of lengthδ(s,v).It must have?nite length since it contains at most|V|?1 edges and each edge has?nite length.By Lemma24.2,v.d=δ(s,v)<∞upon termination.On the other hand,suppose v.d<∞when BELLMAN-FORD ter-minates.Recall that v.d is monotonically decreasing throughout the algorithm, and RELAX will update v.d only if u.d+w(u,v) Chapter21 Michelle Bodnar,Andrew Lohr April12,2016 Exercise21.1-1 EdgeP rocessed initial{a}{b}{c}{d}{e}{f}{g}{h}{i}{j}{k} (d,i){a}{b}{c}{d,i}{e}{f}{g}{h}{j}{k} (f,k){a}{b}{c}{d,i}{e}{f,k}{g}{h}{j} (g,i){a}{b}{c}{d,i,g}{e}{f,k}{h}{j} (b,g){a}{b,d,i,g}{c}{e}{f,k}{h}{j} (a,h){a,h}{b,d,i,g}{c}{e}{f,k}{j} (i,j){a,h}{b,d,i,g,j}{c}{e}{f,k} (d,k){a,h}{b,d,i,g,j,f,k}{c}{e} (b,j){a,h}{b,d,i,g,j,f,k}{c}{e} (d,f){a,h}{b,d,i,g,j,f,k}{c}{e} (g,j){a,h}{b,d,i,g,j,f,k}{c}{e} (a,e){a,h,e}{b,d,i,g,j,f,k}{c} So,the connected that we are left with are{a,h,e},{b,d,i,g,j,f,k}, and{c}. Exercise21.1-2 First suppose that two vertices are in the same connected component.Then there exists a path of edges connecting them.If two vertices are connected by a single edge,then they are put into the same set when that edge is processed. At some point during the algorithm every edge of the path will be processed,so all vertices on the path will be in the same set,including the endpoints.Now suppose two vertices u and v wind up in the same set.Since every vertex starts o?in its own set,some sequence of edges in G must have resulted in eventually combining the sets containing u and v.From among these,there must be a path of edges from u to v,implying that u and v are in the same connected component. Exercise21.1-3 Find set is called twice on line4,this is run once per edge in the graph,so, we have that?nd set is run2|E|times.Since we start with|V|sets,at the end 1 第二章算法入门 由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。另，思考题2-3 关于霍纳规则，有些部分没有完成，故没把解答写上去，我对其 c 问题有疑问，请有解答方法者提供个意见。 给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。 插入排序算法伪代码 INSERTION-SORT(A) 1 for j ← 2 to length[A] 2 do key ←A[j] 3 Insert A[j] into the sorted sequence A[1..j-1] 4 i ←j-1 5 while i > 0 and A[i] > key 6 do A[i+1]←A[i] 7 i ←i ? 1 8 A[i+1]←key C#对揑入排序算法的实现: public static void InsertionSort Chapter6 Michelle Bodnar,Andrew Lohr December31,2016 Exercise6.1-1 At least2h and at most2h+1?1.Can be seen because a complete binary tree of depth h?1hasΣh?1 i=02i=2h?1elements,and the number of elements in a heap of depth h is between the number for a complete binary tree of depth h?1exclusive and the number in a complete binary tree of depth h inclusive. Exercise6.1-2 Write n=2m?1+k where m is as large as possible.Then the heap consists of a complete binary tree of height m?1,along with k additional leaves along the bottom.The height of the root is the length of the longest simple path to one of these k leaves,which must have length m.It is clear from the way we de?ned m that m= lg n . Exercise6.1-3 If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree.So,it is larger than it’s parent,so,the heap property is violated at the parent of the maximum element in the subtree Exercise6.1-4 The smallest element must be a a leaf node.Suppose that node x contains the smallest element and x is not a leaf.Let y denote a child node of x.By the max-heap property,the value of x is greater than or equal to the value of y.Since the elements of the heap are distinct,the inequality is strict.This contradicts the assumption that x contains the smallest element in the heap. Exercise6.1-5 Yes,it is.The index of a child is always greater than the index of the parent, so the heap property is satis?ed at each vertex. 1 Chapter7 Michelle Bodnar,Andrew Lohr April12,2016 Exercise7.1-1 13199512874212611 13199512874212611 13199512874212611 91913512874212611 95131912874212611 95131912874212611 95819121374212611 95871213194212611 95874131912212611 95874131912212611 95874219122113611 95874261221131911 95874261121131912 Exercise7.1-2 If all elements in the array have the same value,PARTITION returns r.To make PARTITION return q= (p+r)/2 when all elements have the same value,modify line4of the algorithm to say this:if A[j]≤x and j(mod2)= (p+1)(mod2).This causes the algorithm to treat half of the instances of the same value to count as less than,and the other half to count as greater than. Exercise7.1-3 The for loop makes exactly r?p iterations,each of which takes at most constant time.The part outside the for loop takes at most constant time.Since r?p is the size of the subarray,PARTITION takes at most time proportional to the size of the subarray it is called on. Exercise7.1-4 To modify QUICKSORT to run in non-increasing order we need only modify line4of PARTITION,changing≤to≥. 1 Chapter2 Michelle Bodnar,Andrew Lohr April12,2016 Exercise2.1-1 314159264158 314159264158 314159264158 263141594158 263141415958 263141415859 Exercise2.1-2 Algorithm1Non-increasing Insertion-Sort(A) 1:for j=2to A.length do 2:key=A[j] 3://Insert A[j]into the sorted sequence A[1..j?1]. 4:i=j?1 5:while i>0and A[i] Chapter2 Getting Start 2.1 Insertion sort 2.1.2 将Insertion-Sort 重写为按非递减顺序排序 2.1.3 计算两个n 位的二进制数组之和 2.2 Analyzing algorithms 当前n-1个元素排好序后，第n 个元素已经是最大的元素了. 最好时间和最坏时间均为2()n Θ 2.3 Designing algorithms 2.3.3 计算递归方程的解 22()2(/2)2,1k if n T n T n n if n for k =?=?+ = >? （1） 当1k =时，2n =，显然有()lg T n n n = （2） 假设当k i =时公式成立，即()lg 2lg 22i i i T n n n i ===?， 则当1k i =+，即12i n +=时， 2.3.4 给出insertion sort 的递归版本的递归式 2.3-6 使用二分查找来替代insertion-sort 中while 循环内的线性扫描，是否可以将算法的时间提高到(lg )n n Θ？ 虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但 是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是2()n Θ 2.3-7 给出一个算法，使得其能在(lg )n n Θ的时间内找出在一个n 元素的整数数组内，是否存在两个元素之和为x 首先利用快速排序将数组排序，时间(lg )n n Θ，然后再进行查找： Search(A,n,x) QuickSort(A,n); i←1; j←n; while A[i]+A[j]≠x and i Chapter19 Michelle Bodnar,Andrew Lohr April12,2016 Exercise19.2-1 First,we take the subtrees rooted at24,17,and23and add them to the root list.Then,we set H.min to18.Then,we run consolidate.First this has its degree2set to the subtree rooted at18.Then the degree1is the subtree rooted at38.Then,we get a repeated subtree of degree2when we consider the one rooted at24.So,we make it a subheap by placing the24node under18. Then,we consider the heap rooted at17.This is a repeat for heaps of degree1, so we place the heap rooted https://www.wendangku.net/doc/4c13772613.html,stly we consider the heap rooted at23,and then we have that all the di?erent heaps have distinct degrees and are done,setting H.min to the smallest,that is,the one rooted at17. The three heaps that we end up with in our root list are: 23 17 38 30 41 and 1 Chapter10 Michelle Bodnar,Andrew Lohr April12,2016 Exercise10.1-1 4 41 413 41 418 41 Exercise10.1-2 We will call the stacks T and R.Initially,set T.top=0and R.top=n+1. Essentially,stack T uses the?rst part of the array and stack R uses the last part of the array.In stack T,the top is the rightmost element of T.In stack R, the top is the leftmost element of R. Algorithm1PUSH(S,x) 1:if S==T then 2:if T.top+1==R.top then 3:error“over?ow” 4:else 5:T.top=T.top+1 6:T[T.top]=x 7:end if 8:end if 9:if S==R then 10:if R.top?1==T.top then 11:error“over?ow” 12:else 13:R.top=R.top?1 14:T[T.top]=x 15:end if 16:end if 1 Algorithm2POP(S) if S==T then if T.top==0then error“under?ow” else T.top=T.top?1. return T[T.top+1] end if end if if S==R then if R.top==n+1then error“under?ow” else R.top=R.top+1. return R[R.top?1] end if end if Exercise10.1-3 4 41 413 13 138 38 Exercise10.1-4 Algorithm3ENQUEUE if Q.head==Q.tail+1,or Q.head==1and Q.tail==Q.length then error“over?ow” end if Q[Q.tail]=x if Q.tail==Q.length then Q.tail=1 else Q.tail=Q.head+1 end if Exercise10.1-5 As in the example code given in the section,we will neglect to check for over?ow and under?ow errors. 2 8.2-4 :在O(1)的时间内，回答出输入的整数中有多少个落在区间[a...b]内。给出的算法的预处理时间为O(n+k) 算法思想：利用计数排序，由于在计数排序中有一个存储数值个数的临时存储区C[0...k]，利用这个数组即可。 #include Chapter16 Michelle Bodnar,Andrew Lohr April12,2016 Exercise16.1-1 The given algorithm would just stupidly compute the minimum of the O(n) numbers or return zero depending on the size of S ij.There are a possible number of subproblems that is O(n2)since we are selecting i and j so that 1≤i≤j≤n.So,the runtime would be O(n3). Exercise16.1-2 This becomes exactly the same as the original problem if we imagine time running in reverse,so it produces an optimal solution for essentially the same reasons.It is greedy because we make the best looking choice at each step. Exercise16.1-3 As a counterexample to the optimality of greedily selecting the shortest, suppose our activity times are{(1,9),(8,11),(10,20)}then,picking the shortest ?rst,we have to eliminate the other two,where if we picked the other two instead,we would have two tasks not one. As a counterexample to the optimality of greedily selecting the task that con?icts with the fewest remaining activities,suppose the activity times are {(?1,1),(2,5),(0,3),(0,3),(0,3),(4,7),(6,9),(8,11),(8,11),(8,11),(10,12)}.Then, by this greedy strategy,we would?rst pick(4,7)since it only has a two con- ?icts.However,doing so would mean that we would not be able to pick the only optimal solution of(?1,1),(2,5),(6,9),(10,12). As a counterexample to the optimality of greedily selecting the earliest start times,suppose our activity times are{(1,10),(2,3),(4,5)}.If we pick the ear-liest start time,we will only have a single activity,(1,10),whereas the optimal solution would be to pick the two other activities. Exercise16.1-4 Maintain a set of free(but already used)lecture halls F and currently busy lecture halls B.Sort the classes by start time.For each new start time which you encounter,remove a lecture hall from F,schedule the class in that room, 1 Chapter35 Michelle Bodnar,Andrew Lohr April12,2016 Exercise35.1-1 We could select the graph that consists of only two vertices and a single edge between them.Then,the approximation algorithm will always select both of the vertices,whereas the minimum vertex cover is only one vertex.more generally,we could pick our graph to be k edges on a graph with2k vertices so that each connected component only has a single edge.In these examples,we will have that the approximate solution is o?by a factor of two from the exact one. Exercise35.1-2 It is clear that the edges picked in line4form a matching,since we can only pick edges from E ,and the edges in E are precisely those which don’t share an endpoint with any vertex already in C,and hence with any already-picked edge. Moreover,this matching is maximal because the only edges we don’t include are the ones we removed from E .We did this because they shared an endpoint with an edge we already picked,so if we added it to the matching it would no longer be a matching. Exercise35.1-3 We will construct a bipartite graph with V=R∪L.We will try to construct it so that R is uniform,not that R is a vertex cover.However,we will make it so that the heuristic that the professor(professor who?)suggests will cause us to select all the vertices in L,and show that|L|>2|R|. Initially start o?with|R|=n?xed,and L empty.Then,for each i from 2up to n,we do the following.Let k= n i .Select S a subset of the vertices of R of size ki,and so that all the vertices in R?S have a greater or equal degree.Then,we will add k vertices to L,each of degree i,so that the union of their neighborhoods is S.Note that throughout this process,the furthest apart the degrees of the vertices in R can be is1,because each time we are picking the smallest degree vertices and increasing their degrees by1.So,once this has been done for i=n,we can pick a subset of R whose degree is one less than the rest of R(or all of R if the degrees are all equal),and for each vertex in 1 Chapter17 Michelle Bodnar,Andrew Lohr April12,2016 Exercise17.1-1 It woudn’t because we could make an arbitrary sequence of MULT IP USH(k),MULT IP OP(k). The cost of each will beΘ(k),so the average runtime of each will beΘ(k)not O(1). Exercise17.1-2 Suppose the input is a1followed by k?1zeros.If we call DECREMENT we must change k entries.If we then call INCREMENT on this it reverses these k changes.Thus,by calling them alternately n times,the total time isΘ(nk). Exercise17.1-3 Note that this setup is similar to the dynamic tables discussed in section 17.4.Let n be arbitrary,and have the cost of operation i be c(i).Then, n i=1c(i)= lg(n) i=1 2i+ i≤n not a power of2 1≤ lg(n) i=1 2i+n=21+ lg(n) ?1+n≤4n?1+n≤5n∈O(n) So,since to?nd the average,we divide by n,the average runtime of each com-mand is O(1). Exercise17.2-1 To every stack operation,we charge twice.First we charge the actual cost of the stack operation.Second we charge the cost of copying an element later on.Since we have the size of the stack never exceed k,and there are always k operations between backups,we always overpay by at least enough.So,the ammortized cost of the operation is constant.So,the cost of the n operation is O(n). Exercise17.2-2 1 1 算法导论第三次习题课 2008.12.17 2 19.1-1 如果x 是根节点：degree[sibling[x]] > sibling[x] 如果x 不是根节点：degree[sibling[x]] = sibling[x] –119.1-3 略 3 19.2-2 过程略( union 操作) 19.2-3 （1）decrease-key （2）extract-min 过程略 19.2-6 算法思想：找到堆中最小值min ，用min-1代替-∞. [遍历堆中树的根节点] 4 15.1-1 15.1-2 略P195 或P329 15.1-4 f i [j]值只依赖f i [j-1]的值，从而可以从2n 压缩为2个。再加上f*、l*、l i [j]。 Print-station(l, I, j ) //i 为线路，j 为station if j>1 then Print-station(l, l i [j], j-1 ) print “line”I, “station”j; 5 15.2-1 略（见课本） 15.2-2 15.2-4 略 MATRIX-CHAIN-MULTIPLY(A, s, i, j) if j>i x= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j), j) y= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j)+1,j) return MATRIX-MULTIPLY(x, y) else return A i 6 15.3-1 （归纳法）递归调用 枚举15.3-2 没有效果，没有重叠子问题 15.3-4 略 (3)n Ο3/2(4/) n n Θ算法导论 第三版 第24章 答案 英
算法导论 第三版 第21章 答案 英
算法导论第二章答案
算法导论 第三版 第六章 答案 英
算法导论 第三版 第七章 答案 英
算法导论 第三版 第二章 答案 英
算法导论习题答案
算法导论 第三版 第十九章 答案 英
Ch10算法导论 第三版 第十章 答案 英
算法导论 第八章答案
算法导论 第三版 第十六章 答案 英
算法导论 第三版 第35章 答案 英
算法导论 第三版 第十七章 答案 英
《算法导论2版》课后答案_加强版2