这是一篇美国的算法设计与分析的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, 8i .
- (10 points) Give pseudocode (and explanation) to reconstruct an LCS from the completed c table and the original sequences X = h x1, x2, . . . , xmi and Y = h y1, y2, . . . , yni 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 v1, v2, . . . , vn 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 vi of maximum weight
Add vi to S
Delete vi 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.
