中原大學89學年度電子工程學系博士招生考試命題

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

系所組別：

電子工程學系

科目：

計算機理論

考試時間：

6月14日第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.	When using the potential method for amortized analysis,If denotes the potential function, c(j) denotes the actual cost of the jth operation,and D(j) denotes the data structure after the first j operations are performaed,then the amortized cost of the jth operation is equal to
c.	In a network,the value of any flow is less then the capacity of any cut.
d.	P is the set of problems solvable with a polynomial time algorthm.If A is in P and problem A reduces to problem B in polynomial time,then B is NP-complete.
e.	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>=n0)
f.	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,
g.	Using adjacency list representation for graph G =(V,E), the Depth-First Search algorithm requires complexity of
h.	If A is NP-hard and A is in NP,then A is NP-complete.

2.	(6%) 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

3.	(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 arrary 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.

(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
<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 your are getting each term from in the recurrence relation.
(b).	Solve the recurrence relation above to get the running time for the overall algorthm. Again,show your work (either by unrolling or by drawing the tree).

5.	(5%)Describe the so-called Pigeonhole Principle.

6.	(5%)Mr.F was murdered.Someone stabbed him by a knife, and we are sure that Mr.F did not stab himself.Only five people can be with F at the time when he was murdered.The five people are, respectively,A ,B ,C ,D ,and E. Of course, all five people claim that they are innocent.Can we apply the Pigeonhole Principle here? If we can, what does the Pigeonhole Principle tell us in this case?

7.	(5%) What is the difference between functions and relations?

8.	(8%)It is possible to build a lattice out of a finite,nonempty set.Describe what this lattice is. In particular, describe(a) what the elements are,(b)what the partial ordering is,(c)what the top and bottom elements are, and (d)what the glb and lub operations are.

9.	(10%)Start by defining what a graph is. Your goal is to define what a DAG is. (Put it another way.First,you must define what a graph is.Then,you define whatever that are needed.Finally, you define what a DAG is.)

10.

(7%)Let X be a nonempty set.Let * be a binary operation on X.

(a)	(2%) What does it mean to say that X is closed under *?(Give the definition.)
(b)	(2%) What does it mean to say that * is associative? (Give the definition.)
(c)	(3%) What does it mean to say, " the inverse always exists " ?(Give the definition.)

11.	(10%) Describe the halting problem,and show that there is no program that can solve the halting problem.

---END---