105成大資聯程設[參考解答]

一、Data Structures (50%)

1. (15%)

We define common friends between node A and node B are the common neighbors of node A and node B. For example, in the above graph the common friends between node 7 and node 10 are node 2 and node 3. Assuming the neighbor list of each node is given, please write a function NumCommonFriend(node A, node B) to return the number of common friends between node A and B in the given graph. Note that you should optimize your code by reducing the number of operations.

參考解答：

int NumCommonFriend(node A, node B)
{
    int arr[13], counter = 0;

    for (int i = 0; i < 13; i++)
        arr[i] = 0;

    for each element in A.neighborList:
        arr[element - 1] = 1;

    for each element in B.neighborList:
        if (arr[element - 1])
            counter++;

    return counter;
}

---

2. (15%) Insert a sequence of values 100, 99, 98, 97, 96, 70, 90, 72, 89 into an empty AVL tree. You will experience x times LL, y times LR, z times RL, and w times RR. Please find (x, y, z, w).

參考解答：(3, 1, 0, 1)

---

3. (20%) Symmetric Min-Max Heap (SMMH) is defined as a complete binary tree, which supports the implementation of double-ended priority queue. The insert, delete-min, and delete-max are three major operations with complexity $O(log n).$ It satisfies the following properties: (1) Root contains no data. (2) Left sibling data $\leq$ Right sibling data (3) If node A has grandparent X, the data in the left child of the node X is equal to or smaller than the data in X (4) If node A has grandparent X, the data in the right child of the node X is equal to or larger than the data in X. Build an SMMH by inserting elements 13, 25, 18, 30, 40, 50, 22, 16, 19, 96 in order. If SMMH is implemented with the array data structure T[] starting with index 1, which represents the root node. Please show T[3] in the final SMMH (5%). If we apply delete-min, please show T[4] in the resulted SMMH (5%). Instead, if we apply delete-max to the original SMMH, please show T[5] in the final SMMH (5%). Please present another two data structures which also support the implementation of double-ended priority queue. (5%)

參考解答：(1) 96 (2) 18 (3) 25 (4) Min-Max Heap, Double-Ended Heap

---

二、Algorithms (50%)

1. (10%) What are the minimum and maximum numbers of elements in a heap of height $h?$

參考解答：If root is in level 1: $min = 2^{h-1}, \, max = 2^h – 1.$

---

2. (15%) The matrix-chain multiplication problem can be stated as follows: Given a chain $(A_1, \, A_2,…, \, A_n)$ of $n$ matrices, where for $i = 1, \, 2,…, \, n,$ matrix $A_i$ has dimension $p_{i-1} \times p_i,$ fully parenthesize the product $A_1A_2…A_n$ in a way that minimizes the number of scalar multiplications. Suppose that you have 6 matrices: $A_1$ has dimension $30 \times 35, \, A_2$ has dimension $35 \times 18, \, A_3$ has dimension $18 \times 5, \, A_4$ has dimension $5 \times 10, \, A_5$ has dimension $10 \times 25, \, A_6$ has dimension $25 \times 30.$ Please calculate the minimum number of scalar multiplications.

參考解答：17900

---

3. (10%) Give a asymptotic tight bound for $T(n) = T(n-1) + lgn.$ Assume that $T(n)$ is constant for sufficiently small $n.$

參考解答：$\Theta (nlgn)$

---

4. (15%) We are given a directed graph $G=(V,E)$ on which each edge $(u,v) \in E$ has an associated value $r(u,v),$ which is a real number in the range $0 \leq r(u,v) \leq 1$ that represents the reliability of a communication channel from vertex $u$ to vertex $v.$ We interpret $r(u,v)$ as the probability that the channel from $u$ to $v$ will not fail, and we assume that these probabilities are independent. Given an efficient algorithm to find the most reliability path between two given vertices.

參考解答：將原本之edges取$-log,$ 則$r(u,v)$還是會$\geq 0,$ 並且新值越小代表越reliable, 所以再用single source shortest path即可求出。

$$\begin{equation} w(u,v) = \begin{cases} -lgr(u,v) & \text{if $r(u,v) > 0$}\\ \infty & \text{if $r(u,v) = 0$} \end{cases} \end{equation}$$

---

試題(pdf)：連結

有任何問題，或想要完整解釋的，歡迎在下方留言唷！