## Data Structure (50%)

### 一、是非題 (15%)

1. Let T be a minimum spanning tree of G. Then, for any pair of vertices s and t, the shortest path from s to t in G is the path from s to t in T.

2. The function $\lceil lgn \rceil !$ is polynomially bounded.

3. If the depth-first search of a graph G yields no back edges, then the graph G is acyclic.

4. Suppose P1 and P2 are problems and P1 $\leq _p$ P2. If P2 can be solved by an algorithm with time complexity $\lceil lglgn \rceil !,$ then P1 $\in P.$

5. Sorting 8 elements with a comparison sort requires 24 comparisons in the worst case.

### 二、計算題 (25%)

1. (10%) Use the recursion-tree method to solve the recurrence $T(n) = 2T(n/2) + n/lgn.$

2. (10%) For COIN-CHANGE problem defined below, please calculate (a) how many different subproblems overall and (b) how many choices we have in determining which subproblem(s) to use in an optimal solution. [COIN-CHANGE Problem: An amount of money $M,$ and an array of $d$ denominations $c = (c_1, \, c_2,…,c_d),$ in a decreasing order of value $(c_1 > c_2 > … > c_4).$ Please find a list of $d$ integers $i_1, \, i_2,…, \, i_d$ such that $c_1 \times i_1 + c_2 \times i_2 + … + c_d \times i_d = M$ and $i_1 + i_2 + … + i_d$ is minimal.]

(a) M
(b) d

3. (15%) Please analysis the running time of Dijkstra’s algorithm under the following data structure implementation (1) array, (2) binary heap, and (3) Fibonacci heap [where Extract-Min $O(lgV),$ Decrease-Key $O(1)$]

(1) $O(V^2)$
(2) $O(ElgV + VlgV)$
(3) $O(VlgV + E)$

## Algorithms (50%)

1. (15%) Consider the following graph:

$$圖片請看原檔$$

Compute minimum cost and construct minimum spanning tree step by step using:
(1) Kruskal’s algorithm
(2) Prim’s algorithm
(3) Sollin’s algorithm

Minimum cost: 64
MST:

2. (15%) Jeremy is a waiter working in a restaurant. The chef there is sloppy; when he prepares a stack of pancakes, they come out all different sizes. When Jeremy delivers the pancakes to the customer, he wants to rearrange them by grabbing several from the top and flipping them over on the way. After repeating this for several times, the smallest pancake is on top, and so on, down to the largest at the bottom. If there are n pancakes, how many flips are required? Design an algorithm to help Jeremy, and analyze its time complexity.

3. (20%) A Bloom Filter is a space-efficient probabilistic data structure used to test whether a key is in a large data set. Instead of answering “yes” or “no,” a Bloom Filter answers “maybe” or “no.” A Bloom Filter consists of m bits of memory and h uniform and independent hash functions $f_1, \, f_2,…, \, f_h.$ Each $f_i$ hashes a key k to an integer in the range $[1, \, m].$ Initially all m filter bits are zero, and the data set is empty. When key k is added to the data set, bits $f_1(k), \, f_2(k),…, \, f_h(k)$ of the filter are set to 1. When a query “Is key k is in the data set?” is made, bits $f_1(k), \, f_2(k),…, \, f_h(k)$ are examined. The query answer is “maybe” if all these bits are 1. Otherwise, the answer is “no.”

(1) When the answer is “no,” the key is not in the data set; when the answer is “maybe,” the key may or may not be in the data set. Explain why.
(2) A filter error occurs whenever the answer is “maybe” and the key is not in the data set. Assume that key k is an integer in the range $[1, \, n]$ and u updates are made. Compute the probability of filter error for an arbitrary query after the u-th update.

(1) 因為不同key值可能對應到相同的memory bit造成就算k沒被加進data set, 還是有機會造成$f_i(k)$ set成1的case.
(2)
With m bits, h hash function, u updates
proability that a certain bit is still 0 after inserted n elements is $(1 – \dfrac{1}{m})^{hu}$
The proability that a certain bit is 1: $1 – (1 – \dfrac{1}{m})^{hu}$
So the proability of filter error is: $(1 – (1 – \dfrac{1}{m})^{hu})^h$

### 6 留言

1. #### Jackson

請問是非5，不是 8 lg 8 = 8 * 3 = 24 嗎 ?

• 文章作者的留言

#### mt

這題要用decision tree，然後有8!個樹葉，因為總共有8!種排法，所以worst case requires $lg(8!)$喔～

2. #### Jackson

Algorithm 3-2 :

With m bits, h hash function, u updates
proability that a certain bit is still 0 after inserted n elements is (1 – 1/m)^(hu)

The proability that a certain bit is 1 :
1 – (1 – 1/m)^(hu)

So the proability of filter error is :
(1 – (1 – 1/m)^(hu))^(h)

3. #### Jackson

想請問非選 4 是怎麼得出來呢 ?
我透過 Strling formula : n ! = √(2πn) * (n/e)^(n) * Θ(1+(1/n))
並代入 lglgn 變成約 √(2π * lgn) * (lglgn/e)^(lglgn)，大概是 (lglgn/e)^(lglgn)
請問這不是指數嗎 ?

• 文章作者的留言

#### mt

$(lglgn)^{lglgn}$取log可以得到$lglgn \cdot lg(lglgn) \leq lglgn \cdot lglgn \leq O(lgn)$所以是polynomial bounded喔！
至於$(lglgn)^2 \leq O(lgn)$也可以透過取log得出：
$2lg(lglgn) \leq lglgn$