这是一篇美国的算法设计与分析的**CS代写**

**Instructions **

- Your encouraged to typeset your submission using LATEX, and submit in PDF format.Name the PDF fifile ‘
*<*your last name*>*HW5.pdf.’

- Your solutions will be graded on
*correctness*and*clarity*. You should only submit work that you believe to be correct.

- You may collaborate with others on this problem set. However, you must
**write up****your own solutions**and**list your collaborators and any external sources**for each problem. Be ready to explain your solutions orally to a member of the course staff if asked.

- For problems that require you to provide an algorithm, you must give a precise description of the algorithm, together with a proof of correctness and an analysis of its running time. You may use algorithms from class as subroutines. You may also use any facts that we proved in class or from the book.

This homework contains 7 questions, for a total of 70 points.

- (10 points) Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is
*h*7, 12, 3, 19, 5, 40, 8*i*.

- (10 points) Give pseudocode (and explanation) to reconstruct an LCS from the completed
*c*table and the original sequences*X*=*h**x*1,*x*2, . . . ,*x**m**i*and*Y*=*h**y*1,*y*2, . . . ,*y**n**i*in*O*(*m*+*n*) time, without using the*b*table.

- (10 points) A
*palindrome*is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1,civic, racecar, and aibohphobia (fear of palindromes). Give an effificient algorithm to fifind the longest palindrome that is a subsequence of a given input string. For example, given the input character, your algorithm should return carac. Argue your algorithm’s correctness, and state its complexity.

- (10 points) Let
*G*= (*V*,*E*) be an undirected graph with*n*nodes. As we saw in class,a subset of the nodes is called an*independent set*(IS) if no two of them are joined by an edge. In the*weighted independent set*problem, a*chain graph**G*= (*V*,*E*) of length*n*with values*v*1,*v*2, . . . ,*v**n*is given, and the goal is to fifind the heaviest IS—i.e., an IS whose total weight is as large as possible.

Give an example to show that the following algorithm *does not always *fifind the heaviest

The ”heaviest-first” greedy algorithm

Set *S *to empty

**While **some node remains in *G *

Pick a node *v**i *of maximum weight

Add *v**i *to *S *

Delete *v**i *and its neighbors from *G *

**EndWhile **

**Return ***S *

- (10 points) Suppose that we redefifine the residual network to disallow edges into
*s*. Argue that the Ford-Fulkerson algorithm still correctly computes a maximum flflow.

- (10 points) A bipartite graph is
*k**-regular*if*|**L**|*=*|**R**|*and every vertex (regardless of which side it is on) has exactly*k*neighbors.

**Prove or refute: **Every *k*-regular bipartite graph has a perfect matching.

- (10 points) Show the execution of the Edmonds-Karp algorithm on the flflow network of Figure 26.1(a) in CLRS.