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.

{:1_158:}