中原大學89學年度資訊工程學系碩士班招生考試命題

私立中原大學八十九學年度碩士班招生考試命題紙

所組別：

資訊工程學系

科目：

資料結構與演算法

考試時間：

4月29日第3節

1.(24%)

For each of the following questions, write T for true and F for false.

a.	Kruskal's algorithm for finding a minimum spanning tree of a weighted, undirected graph is an example of a dynamic programming algorithm.
b.	In a flow network G = (V, E) with capacity and flow functions c and f, it is always the case that c_f(u,v)+c_f(v,u)= c(u,v)+c(v,u) for all u, v V.
c.	When using the potential method for amortized analysis, if denotes the potential function, c(j) denotes the actual cost of the j th operation, and D(j) denotes the data structure after the first j operations are performed, then the amortized cost of the jth operation is equal to c(j)+ (D(j-1))-(D(j)).
d.	In a network, the value of any flow is less then the capacity of any cut.
e.	Using adjacency list representation for graph G = (V, E), the Depth-First Search algorithm requires complexity of O(\|V\|+\|E\|)
f.	P is the set of problems solvable with a polynomial time algorithm. If A is in P and problem A reduces to problem B in polynomial time, then B is NP-complete.
g.	If A is NP-hard and A is in NP, then A is NP-complete.
h.	Algorithm A runs in worst-case time f(n) and B runs in worst-case time g(n). If g(n) = O(f(n)(log n)), then B faster than A for all sufficiently large values of n? (for all n >= n₀ )

2.(6%)

Arrange the following functions into asymptotically ascending order (from lowest to highest order).
n ; 2ⁿ ; n(lg n) ;192 ; sqrt(n) ; n!

3.(10%)

(a)	Let S denote a set of activities. Let each activity i in S be denoted by a tuple (i , s_i, f_i), where si denotes the start time, and f_i denotes the finish time. Use the greedy algorithm to find a maximum-size set of mutually compatible activities for S={(1,4,9),(2,7,11),(3,9,12),(4,6,8),(5,2,5),(6,4,6),(7,6,10),(8,12,13),(9,1,7)}
(b)	Use the greedy algorithm to construct a Huffman code for the following set of characters where the frequency is given after each corresponding character. a:47, b:15, c:14, d:18, e:11, f:6

4.(10%)

Consider the graph G₁ shown in Figure 1.

(a)	Find the depth-first search tree for G₁ using the following rules:
	(i)	start the search at V₁
	(ii)	Among all unvisited vertices reachable from the current vertex, always search the one with minimum index.
(b)	Find the breadth-first search tree for G₁ by starting the search at V₁.

5.(5%)

Apply the Prim's algorithm to construct a minimum-spanning-tree on the following graph. The results must show the sequence of the edges added to the tree, suppose the initial root vertex is “a”?

6.(5%)

Apply the Dijkstra's algorithm which solves the single-source shortest-path problem on the following graph. Suppose “s” is the source. Draw separate updated graphs for the iteration steps

7.(10%)

Show how to sort n integers in the range 1 to n² in O( n ) times.

8.(10%)

Suppose you are given an array of n sorted numbers that has been circularly shifted m positions to the right. For example {36,45,5,18,26,29} is a sorted array that has been circularly shifted m=2 positions to the right. Give an O(log n) algorithm to find the largest number in this array. Note that you don't know what m is.

9.(10 %)

Let G=( V,E ) be a flow network with source s, sink t, and suppose each edge e Є E has capacity c(e) = 1. Assume also that |E| = Ω(V).

(a).	Suppose we implement the Ford-Fulkerson maximum- flow algorithm by using depth-first search to find augmenting paths in the residual graph. What is the worst-case running time of this algorithm on G?
(b).	Suppose a maximum flow for G has been computed, and a new edge with unit capacity is added to E. Describe how the maximum flow can be efficiently updated. Analyze your algorithm.

10.(10%)

Suppose Mergesort was modified such that it splits the list into 3 sections , and then merges the three lists, as follows:
3-way-Mergesort(A:array of integers) returns array of integers
-------------------------------------------------------------------------------------
/* Base cases to the sort */
if (size(A) = 1) then return A
if (size(A) = 2) then
if (A[1] < A[2]) then
return A
else
swap A[1] and A[2]
return A
end if
end if
/* If the list is size 3 or bigger, split the list up */
k = size(A) / 3
B = 3-way-Mergesort(A[1..k])
C = 3-way-Mergesort(A[k+1..2k])
D = 3-way-Mergesort(A[2k+1..size(A)])
/* Now merge the three lists, two at a time */
E = Merge(B,C)
F = Merge(E,D)
/* return the result */
return F
Suppose also that the merge operation, like that used in the normal mergesort, takes time linear to the inputs. Thus, if the merge operation takes lists of size m and n, the merge operation will run in time O(m+n).

(a)	Inspect the code above and determine a recurrence relation for the algorithm. Be sure to show your work, and explain where you are getting each term from in the recurrence relation.
(b)	Solve the recurrence relation above to get the running time for the overall algorithm. Again, show your work (either by unrolling or by drawing the tree).

---END---