NiNi's Den

# Advance-Algorithm::homework6

Words: 2,821Reading time: 13 min
2018/01/15 Share

##### 1. Show that LCD$\leq$ LIS and LCS$\leq$ LIS. Does this result imply that there exist $O(n logn)$ algorithms for LCD and LCS? (Here $n$ represents the input length.)

LCS = Longest Common Subsequence
LCD = Longest Chain of Dominations (平面上一串點，a支配b支配c支配d，求這個平面最長的支配鍊是多長)
LIS = Longest Increasing Subsequence

##### 3. Show that any comparison-based algorithm needs $\Omega(n log n)$ time to solve the following 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.

• Euclidean distance：平面上兩點間的直線距離即為這兩點的Euclidean distance
• 原題目：在2D平面上給定n個點，建一個距離（權重）總和最小的tree，tree的各頂點即為2D平面上的點，兩頂點間的邊的距離（權重）即為這兩的點在平面上的直線距離。
• 直接將問題轉成「最小生成樹」就可以用 Kruskal’s algorithm
• 但作業是：Show that any comparison-based algorithm needs $\Omega(nlogn)$ time to solve this problem
• 參考wiki吧lol
• 利用問題變轉的特性，因為決策版EMST可以變轉為最佳化EMST，求的決策版的下界便可同時知道最佳化EMST的下界

wiki

##### 5. Let $p(x)$ be a given polynomial of degree n in standard form, and let $x_1, x_2, … , x_n$ be n distinct numbers. Give an algorithm to calculate each $p(x_i)$ for $1 \leq i \leq 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.)

$p(x) = f(x)g(x) + r(x)$

$p(x) = f(x)(x-x_i) + r(x)$

##### 6. Given $n$ pairs of points $(x_i, y_i)$ with $x_1, x_2, \dots , x_n$ being distinct. Design an algorithm to find the coefficients of the unique polynomial of degree less than $n$ that passes through these $n$ points.

Neville’s algorithm

• let：$p_{i,j}(x)$ 會穿過 point $i$~$j$ 的多項式
• initial condition：$p_{i,i}(x) = y_i$
• recurrence relation：$p_{i,j}(x) = \frac {(x-x_j)p_{i,j-1}(x) - (x-x_i)p_{i+1,j}(x)} {(x_i-x_j)}$

##### 7. Given two images $A$ and $B$ with $B$ being the smaller one, 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 sum of the squares of the differences of corresponding elements in the overlapped parts of $A$ and $B$. Note that $B$ must completely reside on $A$.

morris

image A:
$$\begin{bmatrix} a_1 & a_2 & a_3 \\ a_4 & a_5 & a_6 \\ a_7 & a_8 & a_9 \end{bmatrix}$$

image B:
$$\begin{bmatrix} b_1 & b_2 \\ b_3 & b_4 \\ \end{bmatrix}$$

$(b_1-a_5)^2 + (b_2-a_6)^2 + (b_3-a_8)^2 + (b_4-a_9)^2 \\ = \sum_{i=1…4}(b_i)^2 + {(a_5)^2 + (a_6)^2 + (a_8)^2 + (a_9)^2} - 2(b_1a_5 + b_2a_6 + b_3a_8 + b_4a_9)$

• 上式的第二項：我們可以邊輸入邊做出另外一個陣列 A’來加快計算:

• $O(nm)$
$$\begin{bmatrix} (a_1)^2 & (a_1)^2+(a_2)^2 & (a_1)^2+(a_2)^2+(a_3)^2 \\ (a_1)^2+(a_4)^2 & (a_1)^2+(a_2)^2+(a_4)^2+(a_5)^2 & 略 \\ (a_1)^2+(a_4)^2+(a_7)^2 & 略 & 略 \end{bmatrix}$$
• 上式的第一項：Image B因為是比較小張的圖片，所以每個元素的平方一定會用到，全部加起來放進一個變數就好了

• $O(pq)$
• 上式的第三項：把兩個圖片的矩陣拉成sequence，然後在sequence後面用0 padding到$2^{\lceil log_2n\rceil}$的長度，就會變成$< a_1,a_2,\dots ,a_N>,< b_1,b_2,\dots, b_N>$，兩個sequence做Cyclic Convolution會得到一個長度為Ｎ的sequence $r$，例：$< 1,2,3,4 >,< 1,2,3,4 >$這兩個sequence會產出$< 30,24,22,24 >$
• $O(NlogN)$

$$30 = (1*1 + 2*2 + 3*3 + 4*4) \\ 24 = (1*4 + 2*1 + 3*2 + 4*3) \\ 22 = (1*3 + 2*4 + 3*1 + 4*2) \\ 24 = (1*2 + 2*3 + 3*4 + 4*1) \\$$

##### 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.

*複雜度分析：

suffix tree及線性時間造樹
GST

dp解，複雜度太高

##### 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.

Example : xabxac的後綴樹

##### 11. Solve the minimum coloring problem on interval graphs.

Interval graph: 用前面活動規劃的問題來舉例，就是把活動轉為graph表示，每個活動為圖上的點，如果兩活動時間有重疊就在兩點間加上邊。

bfs著色，填入不跟鄰近點衝突的最小色號。

##### 12. Design an algorithm for determining $\alpha (G)$ and $k(G)$ on a bipartite graph $G$.

• $\alpha(G)$: 最大獨立集的大小
• $k(G)$: 最小團覆蓋的數量
• ：每個點都是相鄰的，則可以稱為團，即這個團切下來可以看成是一個完全圖
• 最小團覆蓋：使用最少數量的團，來包含這整張圖的頂點
• 二分圖 裡面你只能找到一些由兩個點構成的團。

• 最大獨立集的大小 = 頂點總數($|V|$) - 最大匹配
• 最小團覆蓋 = 最大匹配 + 剩下的獨立點
= 最大匹配數 + (頂點總數 - 2 * 最大匹配)
= 頂點總數 - 最大匹配 = 最大獨立集的大小 !!!
• 二分圖的最大匹配：可用「匈牙利演算法」解
##### 13. A path cover of a directed graph $G=(V, E)$ is a set $P$ of paths such that every vertex in $V$ is included in at least one path in $P$. A minimum path cover of $G$ is a path cover containing the fewest number of paths. Give an algorithm to find a minimum path cover of a directed acyclic graph.

• 最小不可交路徑覆蓋 = 原圖節點數 - 對應的二分圖的最大匹配數

• 最小相交路徑覆蓋：我們可以先幫圖加邊，如果有路徑1->2->3，我們就直接新增一條邊1->3，然後再用最小不可交路徑覆蓋的方法，就可以求得相交路徑覆蓋。

Original Author: Terrynini

Original link: http://blog.terrynini.tw/tw/Advance-Algorithm-homework6/

Publish at: January 15th 2018, 12:23:31

Copyright: This article is licensed under CC BY-NC 4.0