标题: comp6651算法设计2012作业4 [打印本页] 作者: .Concordia百事通 时间: 2014-3-23 21:25 标题: comp6651算法设计2012作业4 Solve the following problems from your textbook (Introduction to Algorithms, second edition, by T.
Cormen, C. Leiserson, R. Rivest, C. Stein, McGraw Hill).
Problem 1: 32.1-2
Suppose that all characters in the pattern P are different. Show how to accelerate NAIVE-
STRING-MATCHER to run in time O(n) on an n-character text T.
Problem 2: 32.2-3
Show how to extend the Rabin-Karp method to handle the problem of looking for a given m × m
pattern in an n × n array of characters. (The pattern may be shifted vertically and horizontally,
but it may not be rotated.)
Problem 3: 34.2-2
Prove that if G is an undirected bipartite graph with an odd number of vertices, then G is
nonhamiltonian.
Problem 4: 34.2-7
Show that the hamiltonian-path problem can be solved in polynomial time on directed acyclic
graphs. Give an efficient algorithm for the problem.
Problem 5: 34.3-1
Verify that the circuit in Figure 34.8(b) is unsatisfiable.
Problem 6: 34.5-6
Show that the hamiltonian-path problem is NP-complete. 作者: mrbear 时间: 2014-4-20 15:17
{:1_158:}