### 一、Data Structures (50%)

1. Answer True or False for the following statements. Give correct answer or explain clearly for False statements. (12%)

(1) Let G be a graph with $e$ edges and $v$ vertices. If $G$ is represented by adjacency matrix, DFS requires $O(e^2)$ time.
(2) 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.$
(3) 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 chaining method.

2. Consider the following AOE network: (18%)

(1) Obtain $e(i)$ and $l(i)$ for all activity $i.$
(2) List all critical activities.
(3) List all critical paths.

(1)

(2) $a_1,a_3,a_4,a_6,a_8,a_9,a_{11}.$
(3) $v_0 \to v_1 \to v_4 \to v_7 \to v_8 \ v_0 \to v_3 \to v_5 \to v_7 \to v_8$

3. Given the following 8 runs: (20%)

(1) Draw the corresponding winner tree.
(2) Draw the restructured winner tree after one record has been output.
(3) Draw the loser tree based on the answer of question (2).
(4) Derive the total required time to merge $n$ records through a winner tree with $k$ runs.

(1)

(2)

(3)

(4) $\Theta(nlgk)$

### 二、Algorithms (50%)

1. (10%) How can we prove the given problem in NP-complete?

(1) Verify that the problem has a non-deterministic algorithm in polynomial time.
(2) Reduce a known NPC problem to the given problem.

2. (10%) Give an algorithm that determines whether or not a given undirected graph $G=(V,E)$ contains a cycle. Your algorithm should run in $O(V)$ time, independent of $|E|.$

(1) Input $G(V,E),$ 令 $S$ 為 source.
(2) If $|E| \geq |V|,$ 則 return “cycle found”.
(3) Else enqueue(S), declare empty set $S = \{\}.$
(4) Dequeue(S), $\forall u \in adjList(v)$ 若 $u \in S,$ 則 return “cycle found”, else $S = S \cup \{v\}.$

(a) 0-1 knapsack problem can be solved by greedy strategy.
(b) In an undirected graph, we can apply the Depth-First-Search algorithm (DFS) to get tree edges and cross edges.
(c) Based on the top-down approach, we can use the memorization to reduce the time.
(d) Unweighted longest simple path problem has the optimal sub-structure.
(e) If we first apply the topology sort to a directed graph and then run the DFS algorithm on this graph, no back edges can be obtained.

4. (10%) Use Master theorem to solve the recurrence $T(n) = T(2n/3) + 1.$

5. (10%) Write the breadth first spanning tree staring at node 0 (visit the smaller number first).