2013-12-30 08:39:24Morris
[高等演算法] 雜II
高等演算法 第 6 次作業
1. Show that LCD≦LIS and LCS≦LIS. Does this result imply that there exist O(n log
n) algorithms for LCD and LCS? (Here n represents the input length.)
// Longest Chain of Dominations(LCD)
=> yes, because of right-side is more difficult than left-side.
=> if we can transfer problem to the right-side, then using right-side's algorithm solve it.
2. Given a set of points S in the plane, a subset of S is called an anti-chain if the points
of the subset can be arranged in an order such that the x coordinates of the points in
the order are increasing and their y coordinates are decreasing. Design an algorithm
to find an anti-chain with maximal size.
=> ley y_new_value = infinite value - y_value for all points.
=> same as LCD problem
3. Show that any comparison-based algorithm needs (n log n) time to solve the
following two problems. (1) The Euclidean minimum spanning tree problem:
given n points in the 2D plane, construct a tree of minimum total length whose
vertices are the given points and the edge length of an edge is the Euclidean distance
between the two end points of the edge. (2) LCD.
(1) sorting_problem <= Euclidean minimum spanning tree problem.
... 看不懂題目
4. Let x1, x2, … , xn be n distinct points. Give an efficient algorithm to calculate the
coefficients of a degree n polynomial p(x) such that p(xi) = 0 for every 1 i n.
=> FFT merge two polynomial - O(n log n)
=> f(x) = (x-x0)*(x-x1)* ... * (xn)
=> T(n) = 2T(n/2) + O(n log n)
=> T(n) = O(n * log n * log n)
5. Let p(x) be a polynomial of degree n, and let x1, x2, … , xn be n distinct numbers.
Give an efficient algorithm to calculate each yi = p(xi) for every 1 i n. (Hint: use
the fact that the division problem of polynomials can be solved in O(n log n) time
and the result of the previous problem.)
f(x) = (x-x1)*(x-x2)* ... * (x-xn)
p1(x) = (x-x1)*(x-x2)*...(x-x(n/2)) * q1(x) + r1(x) // p1(x) = p(x), O(n log n log n)
p2(x) = (x-x(n/2+1))*(x-x(n/2+2))*...(x-xn) * q2(x) + r2(x) // p2(x) = p(x), O(n log n log n)
// solve r1(x1), r1(x2) ..., r1(x(n/2)), r2(xn/2+1), r2(xn/2+2), ..., r2(xn)
// T(n) = 2T(n/2) + O(n log n log n)
// T(n) = O(n log n log n log n)
6. Given n pairs of points (xi, yi) with x1, x2, … , xn being distinct. Design an efficient
time algorithm to find the coefficients of the unique polynomial of degree less than n
that passes through these n points.
p(x) = a1 + a2*(x-x1) + a3*(x-x1)*(x-x2) + ... + an*(x-x1)*(x-x2)*..*(x-xn-1)
-----
not solved.
7. Given two images A and B, use image B to cover image A. Where would we put B
on A, so that the overlapping part of A and B has the most likelihood? The difference
between A and B is defined as the square sum of the differences of corresponding
elements in the overlapped parts of A and B.
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1637
=> FFT
/**
* Given two sequences {a1, a2, a3.. an} and {b1, b2, b3... bn},
* their repeat convolution means:
* r1 = a1*b1 + a2*b2 + a3*b3 + ... + an*bn
* r2 = a1*bn + a2*b1 + a3*b2 + ... + an*bn-1
* r3 = a1*bn-1 + a2*bn + a3*b1 + ... + an*bn-2
* ...
* rn = a1*b2 + a2*b3 + a3*b4 + ... + an-1*bn + an*b1
* Notice n >= 2 and n must be power of 2.
*/
8. Given a set S of k strings, we want to find every string in S that is a substring of
some other string in S. Assume that the total length of all the strings in S is n, give
an O(n) time algorithm to solve this problem.
=> _____$_____#______ ....
=> build suffix tree - O(n)
=> trival tree - O(n) solve that each node record subtree have two different strings.
=> query each string by trival tree - O(n)
9. Give a linear-time algorithm that takes in a string and finds the longest maximal pair
of equal substrings in which the two copies do not overlap. That is, if the two copies
begin at positions p1 < p2 and are of length n', then p1+ n' < p2.
=> build suffix tree - O(n)
=> trival tree - O(n) solve that each node record subtree hava minimum and maximum suffix index.
=> maximum - minimum suffix index >= now_search_string_length.
10. Show how to count the number of distinct substrings of a string T in time O(n),
where the length of T is n. Also show how to enumerate one copy of each distinct
substring in time proportional to the length of all those strings.
=> build suffix tree - O(n)
=> calcuate sum of character on suffix tree node. - O(n)
11. Solve the minimum coloring problem for interval graphs (or see Exercise 16.1-4 in
chapter 16 of the book [CLRS].)
keyword : 區間圖、著色問題
greedy 進行，使用 bfs 盡可能填入不衝突的最小顏色編號。
12. Design an efficient algorithm for determining (G) and k(G) on a bipartite graph G.
分別為最大獨立集和最小團覆蓋數。
最大獨立集 = 頂點總數 - 最大匹配數
最小團覆蓋數 = 二分圖取補圖的最大獨立集 = 頂點總數 - 最大匹配數
// 二分圖取補為 X - Y 有連變沒連，反之亦然。但 Y 集合之間仍沒有邊。
13. Given an nn non-negative matrix W = [wi,j], we want to find an assignment for 2n
variables: u1, u2, … , un and v1, v2, … , vn such that wi,j ui + vj for all i, j, and the
sum 1 i nui + 1 i nvi is minimized.
線性規劃
1. Show that LCD≦LIS and LCS≦LIS. Does this result imply that there exist O(n log
n) algorithms for LCD and LCS? (Here n represents the input length.)
// Longest Chain of Dominations(LCD)
=> yes, because of right-side is more difficult than left-side.
=> if we can transfer problem to the right-side, then using right-side's algorithm solve it.
2. Given a set of points S in the plane, a subset of S is called an anti-chain if the points
of the subset can be arranged in an order such that the x coordinates of the points in
the order are increasing and their y coordinates are decreasing. Design an algorithm
to find an anti-chain with maximal size.
=> ley y_new_value = infinite value - y_value for all points.
=> same as LCD problem
3. Show that any comparison-based algorithm needs (n log n) time to solve the
following two problems. (1) The Euclidean minimum spanning tree problem:
given n points in the 2D plane, construct a tree of minimum total length whose
vertices are the given points and the edge length of an edge is the Euclidean distance
between the two end points of the edge. (2) LCD.
(1) sorting_problem <= Euclidean minimum spanning tree problem.
... 看不懂題目
4. Let x1, x2, … , xn be n distinct points. Give an efficient algorithm to calculate the
coefficients of a degree n polynomial p(x) such that p(xi) = 0 for every 1 i n.
=> FFT merge two polynomial - O(n log n)
=> f(x) = (x-x0)*(x-x1)* ... * (xn)
=> T(n) = 2T(n/2) + O(n log n)
=> T(n) = O(n * log n * log n)
5. Let p(x) be a polynomial of degree n, and let x1, x2, … , xn be n distinct numbers.
Give an efficient algorithm to calculate each yi = p(xi) for every 1 i n. (Hint: use
the fact that the division problem of polynomials can be solved in O(n log n) time
and the result of the previous problem.)
f(x) = (x-x1)*(x-x2)* ... * (x-xn)
p1(x) = (x-x1)*(x-x2)*...(x-x(n/2)) * q1(x) + r1(x) // p1(x) = p(x), O(n log n log n)
p2(x) = (x-x(n/2+1))*(x-x(n/2+2))*...(x-xn) * q2(x) + r2(x) // p2(x) = p(x), O(n log n log n)
// solve r1(x1), r1(x2) ..., r1(x(n/2)), r2(xn/2+1), r2(xn/2+2), ..., r2(xn)
// T(n) = 2T(n/2) + O(n log n log n)
// T(n) = O(n log n log n log n)
6. Given n pairs of points (xi, yi) with x1, x2, … , xn being distinct. Design an efficient
time algorithm to find the coefficients of the unique polynomial of degree less than n
that passes through these n points.
p(x) = a1 + a2*(x-x1) + a3*(x-x1)*(x-x2) + ... + an*(x-x1)*(x-x2)*..*(x-xn-1)
-----
not solved.
7. Given two images A and B, use image B to cover image A. Where would we put B
on A, so that the overlapping part of A and B has the most likelihood? The difference
between A and B is defined as the square sum of the differences of corresponding
elements in the overlapped parts of A and B.
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1637
=> FFT
/**
* Given two sequences {a1, a2, a3.. an} and {b1, b2, b3... bn},
* their repeat convolution means:
* r1 = a1*b1 + a2*b2 + a3*b3 + ... + an*bn
* r2 = a1*bn + a2*b1 + a3*b2 + ... + an*bn-1
* r3 = a1*bn-1 + a2*bn + a3*b1 + ... + an*bn-2
* ...
* rn = a1*b2 + a2*b3 + a3*b4 + ... + an-1*bn + an*b1
* Notice n >= 2 and n must be power of 2.
*/
8. Given a set S of k strings, we want to find every string in S that is a substring of
some other string in S. Assume that the total length of all the strings in S is n, give
an O(n) time algorithm to solve this problem.
=> _____$_____#______ ....
=> build suffix tree - O(n)
=> trival tree - O(n) solve that each node record subtree have two different strings.
=> query each string by trival tree - O(n)
9. Give a linear-time algorithm that takes in a string and finds the longest maximal pair
of equal substrings in which the two copies do not overlap. That is, if the two copies
begin at positions p1 < p2 and are of length n', then p1+ n' < p2.
=> build suffix tree - O(n)
=> trival tree - O(n) solve that each node record subtree hava minimum and maximum suffix index.
=> maximum - minimum suffix index >= now_search_string_length.
10. Show how to count the number of distinct substrings of a string T in time O(n),
where the length of T is n. Also show how to enumerate one copy of each distinct
substring in time proportional to the length of all those strings.
=> build suffix tree - O(n)
=> calcuate sum of character on suffix tree node. - O(n)
11. Solve the minimum coloring problem for interval graphs (or see Exercise 16.1-4 in
chapter 16 of the book [CLRS].)
keyword : 區間圖、著色問題
greedy 進行，使用 bfs 盡可能填入不衝突的最小顏色編號。
12. Design an efficient algorithm for determining (G) and k(G) on a bipartite graph G.
分別為最大獨立集和最小團覆蓋數。
最大獨立集 = 頂點總數 - 最大匹配數
最小團覆蓋數 = 二分圖取補圖的最大獨立集 = 頂點總數 - 最大匹配數
// 二分圖取補為 X - Y 有連變沒連，反之亦然。但 Y 集合之間仍沒有邊。
13. Given an nn non-negative matrix W = [wi,j], we want to find an assignment for 2n
variables: u1, u2, … , un and v1, v2, … , vn such that wi,j ui + vj for all i, j, and the
sum 1 i nui + 1 i nvi is minimized.
線性規劃