算法分析算法复习题（中英文）(3)

递归方程4分

C A T G C 0 0 0 0 0 0 A 0 0 1 1 1 1 C 0 1 1 1 1 2 T 0 1 1 2 2 2 G 0 1 1 2 3 3 A 0 1 1 2 3 3 T 0 1 1 2 3 4 C 0 1 1 2 3 4 G

最长公共子序列长度为4 AGTC 求解过程6分

十二 From the preceding discussion, it suffices to determine the height of a decision tree in which each permutation appears as a reachable leaf. Consider a decision tree of height h with l reachable leaves corresponding to a comparison sort on n elements.

从前面讨论,它可以确定一个决策树的高度,每个排列显示为一个可到达的叶子。考虑一个决策树的高度h和l可及的叶子在n个元素对应于一种比较。

Because each of the n! permutations of the input appears as some leaf,

因为每个n !排列的输入出现一些叶子,

we have n! ≤ l.

Since a binary tree of height h has no more than 2h leaves, 因为一个二叉树的高度

h没有超过2 h叶子

we have（分析5分） n! ≤ l≤ 2h ,

which, by taking logarithms, implies

h ? lg(n!) (since the lg function is monotonically increasing) = ?(n lg n) 列式和求解5分 十三

Proof: If we decompose path p into v1? vi? vj? vk, then we have that w(p) = w(p1i) + w(pij) +w(pjk). Now, assume that there is a path p’ij from vi to vj with weight w(p’ij)< w(pij) . Then, v1? vi? vj? vk is a path from v1 to vk whose weight w(p1i) + w(p’ij) +w(pjk)is less than w(p), which contradicts the assumption that p is a shortest path from v1 to vk.

反证法假设5分，分析5分

十四

列式5分，求解5分 十五

matrix multiplication:

5分

Floyd-Warshall algorithm:

十六

Heapify(A, i) {

l = Left(i); r = Right(i);

if (l <= heap_size(A) && A[l] > A[i]) largest = l; else largest = i;

if (r <= heap_size(A) && A[r] > A[largest]) largest = r; if (largest != i) Swap(A, i, largest); Heapify(A, largest); }

Fixing up relationships between i, l, and r takes ?(1) time，If the heap at i has n elements, the subtrees at l or r can have 2n/3 elements. So time taken by Heapify() is given by T(n) ? T(2n/3) + ?(1) ,by recursive tree, the solution is T(n) = O(lg n) .算法描述4分 列递归方程3分，求解3分