Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

高等演算法 第 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 nn 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.

線性規劃