### 一、Data Structures (50%)

1. Answer True or False for the following statements. Give correct answers for False statements. (30%, 6% for each question)

(1) In static hashing, the worst-case number of comparisons needed for a successful search is $O(n)$ for open addressing. The number could be reduced to $O(logn)$ by using balanced search tree.
(2) Let $d_i$ be the degree of vertex $i$ in a graph $G$ with $|V| = n$ and $|E| = e,$ then $e = \sum_{i = 0}^{n – 1}d_i.$
(3) The path from vertex $u$ to vertex $v$ on a minimal cost spanning tree of an undirected graph $G$ is also a shortest path from $u$ to $v.$
(4) Let $G$ be a graph with $e$ edges and $v$ vertices. If $G$ is represented by adjacency lists, DFS requires $O(ev^2)$ time.
(5) If an AOV network represents a feasible project, its topological order is not unique.

2. 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$ 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.” 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. (10%)

3. Consider the following graph:

Compute minimum cost and construct minimum spanning tree. (10%)

### 二、Algorithms (50%)

1. Is $5^{n + 1} = O(5^n)?$ Is $6^{2n} = O(6^n)?$ (10%)

2. Give asymptotic upper and lower bound for $T(n) = \sqrt{n}T(\sqrt{n}) + n.$ Assume that $T(n)$ is constant for sufficiently small $n.$ Make your bounds as tight as possible. (10%)

3. Show how the time complexity of quicksort can be made to run in $O(nlgn)$ time. (10%)

(1) Find the median of medians x.
(2) Let x be the pivot key and perform normal quicksort.
$T(n) = 2T(\dfrac{n}{2}) + O(n) = O(nlgn).$

4. Determine an Longest Common Subsequence of $<1,0,0,1,0,1,0,1> \text{ and } <0,1,0,1,1,0,1,1,0>.$ (10%)

5. If possible, use the master method to solve $T(n) = 27T(\dfrac{n}{3}) + \Theta(\dfrac{n^3}{lgn}).$ (10%)

### 4 留言

1. #### Jackson

想請問演算法第三題，應該不是 Randomized Quick Sort 的證明 ?
還有資演 2 感覺在 wiki English version 有

• 文章作者的留言

#### mt

我不是用randomized quick sort的證明，不過應該要證那個比較好～感謝！我找找看。

2. #### RRO

不好意思
想請問第一大題第五題
為什麼是true
在特殊例子下
topological也有可能唯一不是嗎@@
因為感覺他的說法太果斷
所以覺得他這樣說也不對

• 文章作者的留言

#### mt

對！題目的資訊太少，應該是false比較合理，感謝～