[試題] 99下 呂學一 資料結構與演算法 期末考消失
課程名稱︰資料結構與演算法下
課程性質︰系內必修
課程教師︰呂學一
開課學院：電機資訊學院
開課系所：資訊工程學系
考試日期（年月日）︰2011/06/17
考試時限（分鐘）：180 min
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
貳零壹壹年陸月壹拾柒日玖點拾分起參小時
說明：每題二十分。可按任何順序答題。題目難度不均，慎選答題順序。
第一題
Turn your NTU ID number into a binary string S according to the following
rules and then draw the suffix tree T of S according to Ukkonen's algorithm:
(1) Turn each English letter (e.g., B) and each even digit (e.g., 8) into 01
(2) Turn each odd digit (e.g., 9) into 10.
For instance, the binary string S for B98765432 is 011001100110011001.
No need to show the intermediate steps. Only your final tree counts.
Remember to show the suffix links and the edge labels.
第二題
Let X be an m-bit binary string. Let Y be an n-bit binary string.
Assume that the suffix tree of X (together with its suffix links) can be
computed in Ο(m) time and Ο(n) space.
You are asked to prove that it takes Ο(m + n) time and Ο(m) space
to compute a longest common substring of X and Y.
第三題
Given a graph G and a positive integer k, the maximum clique problem is to
determine whether G contains a k-node complete subgraph.
Prove that the maximum clique problem is NP-complete by doing the following
two steps.
(1) Show that the maximum clique problem belongs to the class NP.
Specifically, you are asked to give a non-deterministic polynomial-time
algorithm for correctly solving the maximum clique problem.
Do not forget to show that your non-deterministic algorithm does correctly
solve the maximum clique problem and does run in polynomial time.
(2) Show that the maximum clique problem is NP-hard by a polynomial-time
reduction from the 3-SAT problem.
Specifically, you have to prove that for any 3-SAT ψ，it takes polynomial
time to compute a graph G(ψ) and a positive integer k(ψ) such that ψ is
satisfiable if and only if G(ψ) contains k(ψ)-node complete subgraph.
Note that you have to explicitly describe what G(ψ) and k(ψ) are.
That is, your polynomial-time reduction has to be directly from 3-SAT.
第四題
Let S be an array of n distinct numbers.
The range minima tree of S is the n-node binary tree rooted at S[i] = min S
whose left subtree is the range minima tree of S[1...i-1] and whose right
subtree is the range minima tree of S[i+1...n].
Give an Ο(n)-time algorithm for computing the range minima tree of any
n-number array of S. Do not forget to justify and analyze your algorithm.
第五題
Given an n-node m-edge graph G, the vertex cover problem is to find a set S
of nodes with minimum |S| such that each edge of G is incident to at least
one node of S. A greedy algorithm for the vertex cover problem is as follows.
It starts by letting S be the empty set. It then repeats the following two
steps until G has no edges and output the final S:
(1) a node u with maximum degree in the current G is inserted into S, and
(2) all edges incident to u in the current G are deleted from G.
You are asked to prove that the greedy algorithm is an Ο(log n)-approximation
algorithm for the vertex cover problem.
Specifically, you have to show that the algorithm always outputs in polynomial
time a vertex cover S of G that satisfies |S| = Ο(log n)．|S*| for any vertex
cover S* of G.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.117.127.210
※ 編輯: paul112004 來自: 59.117.127.210 (06/18 22:03)
→
06/18 22:39, , 1F
06/18 22:39, 1F
推
06/19 00:13, , 2F
06/19 00:13, 2F