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

of matrices, where for i=1，2…，n, matrix Ai has dimension

P i-1? Pi, fully parenthesize the product A1,A2,…,An in a way that minimizes the number of scalar multiplication. We pick as our subproblems the problems of determining the minimum cost of a parenthesization of Ai Ai+1 Aj for 1 ≤ i ≤ j ≤ n. Let m[i, j] be the minimum number of scalar multiplications needed to compute the matrix Ai..j; for the full problem, the cost of a cheapest way to compute A1..n would thus be m[1, n]. Can you define m[i, j] recursively? Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is <4,3,5,2,3>

十一 In the longest-common-subsequence (LCS) problem, we are given two sequences X = and Y = and wish to find a maximum-length common subsequence of X and Y. Please write its recursive formula and determine an LSC of Sequence S1=ACTGATCG and sequence S2=CATGC. Please fill in the blanks in the table below.

C A T G C A C T G A T C G

十二 Proof: Any comparison sort algorithm requires Ω(nlgn) comparisons in the worst case.

How many leaves does the tree have? （叶节点的数目）

–At least n! (each of the n!permutations if the input appears as some leaf) ?n! ≤l（至少n! 个，排列）–At most 2hleaves （引理，至多2h个）?n! ≤l ≤2h ?

h ≥lg(n!) = ?(nlgn)

十三Proof: Subpaths of shortest paths are shortest paths.

Given a weighted, directed graph G = (V, E) with weight function w : E → R, let p = be a shortest path from vertex v1 to vertex vk and, for any i and j such that 1 ≤ i ≤ j ≤k, let pij = be the subpath of p from vertex vi to vertex vj . Then, pij is a shortest path from vi to vj.

十四Proof : The worst case running time of quicksort is Θ(n2)

十五Compute shortest paths with matrix multiplication and the Floyd-Warshall algorithm for the following graph.

十六 Write the MAX-Heapify() procedure to for manipulating max-heaps. And analyze the running time of MAX-Heapify().

三（10分) 1 CountingSort(A, B, k) 2 for i=1 to k 3 C[i]= 0; 4 for j=1 to n 5 C[A[j]] += 1; 6 for i=2 to k 7 C[i] = C[i] + C[i-1]; 8 for j=n downto 1 9 B[C[A[j]]] = A[j]; 10 C[A[j]] -= 1; 四

算法描述3分

The best-case running time is T(n) = c1n + c2(n - 1) + c4(n - 1) + c5(n - 1) + c8(n - 1) = (c1 + c2 + c4 + c5 + c8)n - (c2+ c4 + c5 + c8). This running time can be expressed as an + b for constants a and b that depend on the statement costs ci ; it is thus a linear function of n.

This worst-case running time can be expressed as an2 + bn + c for constants a, b, and c that again depend on the statement costs ci ; it is thus a quadratic function of n. 分析2分

算法描述2分

Θ(1) if n = 1

T(n) =

2T(n/2) + Θ(n) if n > 1.

递归方程和求解3分 五

7 RAND-SELECT(A, p, r, i) (5分) if p = r then return A[p]

q ← RAND-PARTITION(A, p, r) k ← q – p + 1

if i = k then return A[q] if i < k

then return RAND-SELECT(A, p, q – 1, i ) else return RAND-SELECT(A, q + 1, r, i – k )

Randomized RANDOMIZED-PARTITION(A; p; r) (5分) { i ←RANDOM(p, r) exchange A[r] ← A[i]

return PARTITION(A; p; r)} PARTITION(A; p; r) { x← A[r] i ←p-1

for j ← p to r-1

do if A[j] ≤ x then i ←i+1

exchange A[i] ?A[j] exchange A[i+1] ? A[r]

return i+1 } 六

首先画出它对应的图，加上标号，假设从1出发，每次贪心选择一个权重最小的顶点作为下一个要去的城市。(算法策略5分)

求解过程5分 七

100 55 a:4 525 30 d:1630 f: 514 c:1 2b:1 3e: 9 a:1 b:100 c:101 d:111 e:1100 f:1101

八 V={11,21,31,33,43,53,55,65} weight W={1,11,21,23,33,43,45,55}

1121313343535565??????按照单位重量的价值排序，?，然后按照该顺

111212333434555序往背包中放。 九

递归方程4分

f1[1]=9 f2[1]=12 f1[2]=18 f2[2]=16 f1[3]=20 f2[3]=22 f1[4]=24 f2[4]=25 f1[5]=32 f2[5]=30 f1[6]=35 f2[6]=37

the fastest time is 38 and the fastest way is: station 1:line 1 station 2:line 2 station 3:line 1 station 4:line 2 station 5: line 2 station 6: line 1 求解过程6分 十

递归方程4分

m[1,1]=0 m[2,2]=0 m[3,3]=0 m[4,4]=0 m[1,2]=m[1,1]+m[2,3]+p0*p1*p2=60 m[2,3]=m[2,2]+m[3,3]+p1*p2*p3=30 m[3,4]=m[3,3]+m[4,4]+p2*p3*p4=30

m[1,3]=min{m[1,2]+m[3,3]+p0*p2*p3, m[1,1]+m[2,3]+p0*p1*p3}=54 m[2,4]=min{m[2,3]+m[4,4]+p1*p3*p4, m[2,2]+m[3,4]+p0*p2*p4}=48 m[1,4]=min{m[1,1] +m[2,4]+p0*p1*p4, m[1,2]+m[3,4]+p0*p2*p4, m[1,3]+m[4,4]+p0*p3*p4}=78

((A1(A2A3))A4) 求解过程6分 十一

if x[i]?y[j],?c[i?1,j?1]?1 c[i,j]???max(c[i,j?1],c[i?1,j])otherwise