###### tags: `Algorithm` `CLRS 3`
# CH15
## Exercise
### 15.1-1
### Show that equation $(15.4)$ follows from equation $(15.3)$ and the initial condition $T(0) = 1$.
$$(15.3) => T(n) = 1 + \sum_{j=0}^{n-1}T(j)$$
$$(15.4) => T(n) = 2^n$$
PS.直接寫出來會死484
$$T(j) = 2^j$$
$$T(n) = 1 + \sum_{j=0}^{n-1}2^j$$
使用等比級數和公式
$$T(n) = 1 + \frac{2^n - 1}{2-1}$$
$$ T(n) = 2 ^n $$
$$完成 ^ O ^$$
### 15.1-2
### Show, by means of a counterexample, that the following “greedy” strategy does not always determine an optimal way to cut rods. Define the $density$ of a rod of length $i$ to be $Pi/i$, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length $i$ ,where $1 \leq i \leq n$ , having maximum density. It then continues by applying the greedy strategy to the remaining piece of length $n - i$
如果鋼條的售價為：
| 1cm | 2cm | 3cm |
| -------- | -------- | -------- |
| 1 元 | 5 元 | 7 元 |
使用greedy strategy時，若要販售4cm的鋼條則會因為只關注眼前的3cm要如何接成4cm而沒有去檢查實際的最優解其實是2cm+2cm。
$$完成 ^ O ^$$
### 15.1-3
### Consider a modification of the rod-cutting problem in which, in addition to a price $Pi$ for each rod, each cut incurs a fixed cost of $c$. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem.
<s>台灣奴工不需要錢。</s>
每個回合減一次人力費用即可
```cpp=
int modify_bottom_up_cut_rod(vector<int> &vec, int n, int labor){
vector<int> vec2(n + 1, 0);
for(int i = 1; i <= n; i++){
int q = -1;
for(int j = 1; j <= i; j++){
q = max(q, vec[j - 1] + vec2[i - j] - labor);
}
cout << q << endl;
vec2[i] = q;
}
return vec2[n];
}
```
$$完成 ^ O ^$$
### 15.1-4
### Modify MEMOIZED-CUT-ROD to return not only the value but the actual solution,too.
未完成
```cpp=
int memorized_cut_rod_Aux(vector<int> &vec, vector<int> &vec1, int n){
int q;
if((vec1[n] >= 0)){
return vec1[n];
}
if(n == 0){
q = 0;
}
else{
q = -1;
for(int i = 0; i < n; i++){
q = max(q, vec[i] + memorized_cut_rod_Aux(vec, vec1, n - i - 1));
}
}
vec1[n] = q;
return q;
}
int
```
### 15.-5
### he Fibonacci numbers are defined by recurrence (3.22). Give an $O(n)$-time dynamic-programming algorithm to compute the $n$th Fibonacci number. Draw the subproblem graph. How many vertices and edges are in the graph?
```cpp=
int fibonacci(n){
vector<int> vec;
vec.clear();
fibo.push_back(0);
fibo.push_back(1);
for(int i = 2; i <= n; i++){
fibo.push_back(fibo[i - 1] + fibo[i - 2]);
}
return fibo[n];
}
```
懶得檢查
draw subproblem graph
vertice:
$vertice(n) = 1 + n$
edge：
$if\,( n <= 1)$
$\,\,\,\,edge(n) == 0$
$else$
$\,\,\,\,edge(n) = 2\cdot n - 2$
### 15.2-1
### Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is $(5, 10, 3, 12, 5, 50, 6)$.
$$A1 = (5\times10),A2 =(10\times3), A3 = (3\times12),A4 =(12\times5),A5 = (5\times50)(50\times6)$$
| | 1 | 2 | 3 | 4 | 5 | 6|
|-- | -- | -- | -- |-- | - |-|
| 1 | 0 | 150 | 330 | 405 | 1655 |2010 |
| 2 | | 0 | 360 | 330 | 2430 |1950 |
| 3 | | | 0 | 180 | 930 |1770 |
| 4 | | | | 0 | 3000 |1860 |
| 5 | | | | | 0 |1500 |
| 6 | | | | | |0 |
| | 1 | 2 | 3 | 4 | 5 | 6|
|-- | -- | -- | -- |-- | - |-|
| 1 | | 1 | 2 | 2 | 4 |2 |
| 2 | | | 2 | 2 | 2 |2 |
| 3 | | | | 3 | 4 |4 |
| 4 | | | | | 4 |4 |
| 5 | | | | | |5 |
$$(A1A2)[(A3A4)(A5A6)]$$
$$完成 ^ O ^$$
### 15.2-2
### Give a recursive algorithm $\text{MATRIX-CHAIN-MULTIPLY}(A, s, i, j)$that actually performs the optimal matrix-chain multiplication, given the sequence of matrices $\langle A_1, A_2, \ldots ,A_n \rangle$ the stable computed by $\text{MATRIX-CHAIN-ORDER}$, and the indices $i$ and $j$. (The initial call would be $\text{MATRIX-CHAIN-MULTIPLY}(A, s, 1, n)$.)
拿print_optimal_parens改一改即可
```cpp=
int matrix_chain_multiple_rec(vector<int> vec, vector<int> vec2, int i, int j){
if(i == j){
return A[i];
}
else{
return matrix_chain_multiple_rec(vec, vec2, i, s[i][j])*matrix_chain_multiple_rec(vec. vec2, s[i][j] + 1, j)
}
}
```
$$完成 ^ O ^$$
### 15.2-3
### Use the substitution method to show that the solution to the recurrence $\text{(15.6)}$ is $\Omega(2^n)$.
與15.1-1相同的技巧
$(15.6) => if\,(n = 1) P(n) = 1\\else\,P(n) = \sum_{k=1}^{n-1}P(k)*P(n - k)$
$$P(n) = \sum_{k=1}^{n-1}P(k)*P(n - k) \geq 2^n$$
$$\sum_{k=1}^{n-1}2^n*2^{n - k} \geq 2^n$$
$$2^n\sum_{k=1}^{n-1}2^n*2^{n - k}$$
$$2^n\sum_{k=1}^{n-1}1$$
$$2^n(n - 1)\geq2^{n}$$
### 15.2-4
### Describe the subproblem graph for matrix-chain multiplication with an input chain of length $\text n$. How many vertices does it have? How many edges does it have, and which edges are they?
在建表時總共會填$\frac{n(n + 1)}{2}$個格子，代表有$\frac{n(n + 1)}{2}$個vertices。
回憶一下見表的過程中每填一格會有幾個可能的計算方式需要考慮，你會發現可以寫成這樣的式子
$$2(n - 1) , 4(n - 2) , 6(n - 3) , ...$$
全部加起來寫成通式後
$$\sum_{i = 1}^{n - 1}2\cdot i(n - i)$$
$$2\sum_{i = 1}^{n - 1}i(n - i)$$
$$2\sum_{i = 1}^{n - 1}n\cdot i - i^2$$
窩懶惰
$$\frac{n(n+1)(n-1)}{6}$$
$$完成 ^ O ^$$
### 15.2-5
### Let $R(i, j)$ be the number of times that table entry m[i, j] is referenced while computing other table entries in a call of $\text MATRIX-CHAIN-ORDER$. Show that the total number of references for the entire table is
$\sum_{i = 1}^{n}\sum_{j = i}^{n}R(i, j) = \frac{n^3 - n}{3}$
($\textit Hint$: You may find equation $\text(A.3)$useful.)
看起來應該是算時間複雜度
所以請回憶一下虛擬碼最外層的迴圈從$2$到$n$，所以是$\sum_{l = 2}^{n}$，第二層迴圈是$1$到$n - l - 1$，所以是$\sum_{i = 1}^{n - l -1}$，第三層則是$i$到$j - 1$，所以是$\sum_{k = i}^{i + l - 2}2$ (PS: $j = i + l - 1$)合起來會是$\sum_{l = 2}^{n}\sum_{i = 1}^{n - l -1}\sum_{k = i}^{i + l - 2}2$，通過運算會得到$\frac{n^3 - n}{3}$
$$完成 ^ O ^$$
### 15.2-6
### Show that a full parenthesization of an $n$-element expression has exactly $n - 1$ pairs of parentheses.
看起來是要數括號，意味がわからない
假如我們有個$(n + 1)$個元素，則存在一個k可將元素劃分為$B = (A_1, A_2, ...A_k)$ 和$C = (A_{k+1}, A_{k+2},...A_{n + 1})$，那麼B就會有$k - 1$個括號，C則有$n + 1 - (k + 1)$，然後再加上括住全部的括號，就會有$n$個括號，所以括號對數會比元素少1。
窩到底在幹嘛
### 15.3-1
### Which is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem: enumerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running $\text{RECURSIVE-MATRIX-CHAIN}$? Justify your answer.
若要窮舉所有方法需要$2^n$(polynimial time的時間)，若使用$\text{RECURSIVE-MATRIX-CHAIN}$則會是$n\cdot n^3 = n^4$
多一個n為遞迴合併時所需時間
大概ㄅ
### 15.3-2
### Draw the recursion tree for the $\text{MERGE-SORT}$ procedure from Section 2.3.1 on an array of 1616 elements. Explain why memoization fails to speed up a good divide-and-conquer algorithm such as $\text{MERGE-SORT}$.
### 15.3-3
### Consider a variant of the matrix-chain multiplication problem in which the goal is to parenthesize the sequence of matrices so as to maximize, rather than minimize, the number of scalar multiplications. Does this problem exhibit optimal substructure?
可以，矩陣相乘的最大次數也會有最佳子結構
$$完成 ^ O ^$$
### 15.3-4
### As stated, in dynamic programming we first solve the subproblems and then choose which of them to use in an optimal solution to the problem. Professor Capulet claims that we do not always need to solve all the subproblems in order to find an optimal solution. She suggests that we can find an optimal solution to the matrix-chain multiplication problem by always choosing the matrix $A_{k}$ at which to split the subproduct$A_i, A_{i+1}, ..., A_j$(by selecting $k$ to minimize the quantity $P_{i - 1}P_kP_j$) before solving the subproblems. Find an instance of the matrix-chain multiplication problem for which this greedy approach yields a suboptimal solution.
假如$A_1 = 5 \times 6$，$A_2 = 6 \times 3$，$A_3 = 3 \times 2$，若使用Professor Capulet 的方式會得到$((A_1A_2)A_3) = 120$，但最佳解為$(A_1(A_2A_3)) = 96$
$$完成 ^ O ^$$
### 15.3-5
### Suppose that in the rod-cutting problem of Section 15.1, we also had limit $l_i$ on the number of pieces of length $i$ that we are allowed to produce, for $i = 1, 2, \ldots n$. Show that the optimal-substructure property described in Section 15.1 no longer holds.
### 15.3-6
### Imagine that you wish to exchange one currency for another. You realize that instead of directly exchanging one currency for another, you might be better off making a series of trades through other currencies, winding up with the currency you want. Suppose that you can trade nn different currencies, numbered $1, 2, \ldots, n$, where you start with currency $1$ and wish to wind up with currency $n$. You are given, for each pair of currencies $i$ and $j$ , an exchange rate $r_{ij}$, meaning that if you start with dd units of currency ii , you can trade for $dr_{ij}$ units of currency $j$. A sequence of trades may entail a commission, which depends on the number of trades you make. Let $c_{k}$ be the commission that you are charged when you make $k$ trades. Show that, if $c_k$ = 0 for all $k = 1, 2, \ldots, n$, then the problem of finding the best sequence of exchanges from currency $1$ to currency $n$ exhibits optimal substructure. Then show that if commissions $c_k$ are arbitrary values, then the problem of finding the best sequence of exchanges from currency $1$ to currency $n$ does not necessarily exhibit optimal substructure.
### 15.4-1
### Determine an $\text{LCS}$ of $\langle 1, 0, 0, 1, 0, 1, 0, 1 \rangle$ and $\langle 0, 1, 0, 1, 1, 0, 1, 1, 0 \rangle$.
$\langle 1, 0, 0, 1, 1, 1 \rangle$
感覺有很多答案
### 15.4-2
### Give pseudocode to reconstruct an $\text{LCS}$ from the completed $c$ table and the original sequences $X = \langle x_1, x_2, \ldots, x_m \rangle$ and $Y = \langle y_1, y_2, \ldots, y_n \rangle$ in $O(m + n)$ time, without using the $b$ table.
修改print_LCS，table $b$是要記錄你的table $c$ 的內容怎麼來的，跟主程式結合一下就可以了
```
print_LCS_no_b_table(X, Y, c, m, n){
if(c[i][j] == 0){
return
}
else if(X[i] == Y[i]){
print_LCS_no_b_table(X, Y, c, m - 1, n - 1){
print(X[i])
}
}
else if(c[i - 1][j] >= c[i][j - 1]){
print_LCS_no_b_table(X, Y, c, m - 1, n)
}
else{
print_LCS_no_b_table(X, Y, c, m, n - 1)
}
}
```
### 15.4-3
### Give a memoized version of $\text{LCS-LENGTH}$ that runs in $O(mn)$ time.
意味がわからない
### 15.4-4
### Show how to compute the length of an $\text{LCS}$ using only $2 \cdot \min(m, n)$ entries in the $c$ table plus $O(1)$ additional space. Then show how to do the same thing, but using $\min(m, n)$ entries plus $O(1)$ additional space.
一般的LCS再計算$c[i][j]$時需要$c[i - 1][j - 1]$、$c[i - 1][j]$、$c[i][j - 1]$，假如一直都沒有相同字串的話就會只用到$c[i - 1][j]$、$c[i][j - 1$，所以會是$2 \cdot \min(m, n)$。若要降到$\min(m, n)$我們可以逐步釋放不需要(前面)的空間。
### 15.4-5
### Give an $O(n^2)-time$ algorithm to find the longest monotonically increasing subsequence of a sequence of nn numbers.
有點超出學校課程範圍，寒假再說ㄅ
### 15.4-6
### Give an $O(n\lg n)-time$ algorithm to find the longest monotonically increasing subsequence of a sequence of $n$ numbers. ($\textit{Hint:}$ Observe that the last element of a candidate subsequence of length $i$ is at least as large as the last element of a candidate subsequence of length $i - 1$. Maintain candidate subsequences by linking them through the input sequence.)
同上
### 15.5-1
### Write pseudocode for the procedure $\text{CONSTRUCT-OPTIMAL-BST}(root)$ which, given the table $root$, outputs the structure of an optimal binary search tree. For the example in Figure 15.10, your procedure should print out the structure.
k2 is the root
k1 is the left child of k2
d0 is the left child of k1
d1 is the right child of k1
k5 is the right child of k2
k4 is the left child of k5
k3 is the left child of k4
d2 is the left child of k3
d3 is the right child of k3
d4 is the right child of k4
d5 is the right child of k5
corresponding to the optimal binary search tree shown in Figure 15.9(b).
```
CONSTRUCT-OPTIMAL-BST(root, i, j, last){
if(i == j){
return;
}
if(last == 0){
print root[i][j] + "is the root";
}
else if(j < last){
print root[i][j] + "is the left child of " + last;
}
else{
print root[i][j] + "is the right child of " + last;
}
CONSTRUCT-OPTIMAL-BST(root, i, root[i][j] - 1, root[i][j]);
CONSTRUCT-OPTIMAL-BST(root, root[i][j] + 1, j, root[i][j]);
}
```
### 15-5-2
### Determine the cost and structure of an optimal binary search tree for a set of $n = 7$ keys with the following probabilities.
| i | 0 | 1 |2|3|4|5|6|7|
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| $pi$ | | 0.04 |0.06 |0.08 |0.02 |0.10 |0.12 |0.14 |
| $qi$ | 0.06 | 0.06 |0.06 | 0.06 |0.05 |0.05 |0.05 |0.05 |
k2 is the root
k1 is the left child of k2
d0 is the left child of k1
d1 is the right child of k1
k5 is the right child of k2
k4 is the left child of k5
k3 is the left child of k4
d2 is the left child of k3
d3 is the right child of k3
d4 is the right child of k4
d5 is the right child of k5
### 15.5-3
Suppose that instead of maintaining the table $w[i, j]$, we computed the value of $w(i, j)$ directly from equation $\text{(15.12)}$ in line 9 of $\text{OPTIMAL-BST}$ and used this computed value in line 11. How would this change affect the asymptotic running time of $\text{OPTIMAL-BST}$?
$$(15.12) => w(i, j) = \sum_{l = i}^{j}p_l +\sum_{l = i - 1}^{j}q_l$$
感覺只是兩行合併成一行 running time應該不會有變化仍是$O(n^3)$
### 15.5-4
### Knuth [212] has shown that there are always roots of optimal subtrees such that $root[i, j - 1] \le root[i, j] \le root[i + 1, j]$ for all $1 \le i < j \le n$. Use this fact to modify the $\text{OPTIMAL-BST}$ procedure to run in $\Theta(n^2)$ time.
高德納說啥就照做ㄅ。
```
optimal_bst(p, q, n){
let e[1:n, 0:n], w[1:n + 1, 0, n], root[1:n, 1:n] be a new table;
for i = 1 to n + 1:
e[i, i - 1] = q[i - 1];
w[i, i - 1] = q[i - 1];
for i = 1 to n - l - 1:
j = i + l - 1;
e[i, j] = INT_MAX;
w[i, j] = w[i, j] + p[j] + q[j];
for r = root[i, j - 1] to root[i + 1, j]:
t = e[i, r - 1] + e[r + 1, j] + w[i, j];
if t < e[i, j]:
e[i, j] = t;
root[i, j] = r;
return e, root;
}
```
### 參考資料
https://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html
https://walkccc.me/CLRS/
Sign in with Wallet
Connect another wallet