### 一、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, 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. (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 in the final SMMH (5%). If we apply delete-min, please show T in the resulted SMMH (5%). Instead, if we apply delete-max to the original SMMH, please show T in the final SMMH (5%). Please present another two data structures which also support the implementation of double-ended priority queue. (5%)

### 二、Algorithms (50%)

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

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.

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

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.

$$\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}$$