Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 69
Текст из файла (страница 69)
Our criterion of"neatness" is as follows. If a given line contains words i through j, where i ≤ j, and we leaveexactly one space between words, the number of extra space characters at the end of the lineis, which must be nonnegative so that the words fit on the line. We wish tominimize the sum, over all lines except the last, of the cubes of the numbers of extra spacecharacters at the ends of lines. Give a dynamic-programming algorithm to print a paragraph ofn words neatly on a printer.
Analyze the running time and space requirements of youralgorithm.Problems 15-3: Edit distanceIn order to transform one source string of text x[1 m] to a target string y[1 n], we canperform various transformation operations. Our goal is, given x and y, to produce a series oftransformations that change x to y. We use an array z—assumed to be large enough to hold allthe characters it will need—to hold the intermediate results.
Initially, z is empty, and attermination, we should have z[j] = y[j] for j = 1, 2, ..., n. We maintain current indices i into xand j into z, and the operations are allowed to alter z and these indices. Initially, i = j = 1. Weare required to examine every character in x during the transformation, which means that atthe end of the sequence of transformation operations, we must have i = m + 1.There are six transformation operations:••••••Copy a character from x to z by setting z[j] ← x[i] and then incrementing both i and j.This operation examines x[i].Replace a character from x by another character c, by setting z[j] ← c, and thenincrementing both i and j.
This operation examines x[i].Delete a character from x by incrementing i but leaving j alone. This operationexamines x[i].Insert the character c into z by setting z[j] ← c and then incrementing j, but leaving ialone. This operation examines no characters of x.Twiddle (i.e., exchange) the next two characters by copying them from x to z but inthe opposite order; we do so by setting z[j] ← x[i + 1] and z[j + 1] ← x[i] and thensetting i ← i + 2 and j ← j + 2. This operation examines x[i] and x[i + 1].Kill the remainder of x by setting i ← m + 1. This operation examines all characters inx that have not yet been examined. If this operation is performed, it must be the finaloperation.As an example, one way to transform the source string algorithm to the target string altruisticis to use the following sequence of operations, where the underlined characters are x[i] andz[j] after the operation:Operationxzinitial strings algorithm _copyalgorithm a_copyalgorithm al_replace by t algorithm alt_deletealgorithm alt_copyalgorithm altr_insert ualgorithm altru_insert ialgorithm altrui_insert salgorithm altruis_twiddlealgorithm altruisti_insert calgorithm altruistic_killalgorithm_ altruistic_Note that there are several other sequences of transformation operations that transformalgorithm to altruistic.Each of the transformation operations has an associated cost.
The cost of an operationdepends on the specific application, but we assume that each operation's cost is a constant thatis known to us. We also assume that the individual costs of the copy and replace operationsare less than the combined costs of the delete and insert operations; otherwise, the copy andreplace operations would not be used. The cost of a given sequence of transformationoperations is the sum of the costs of the individual operations in the sequence. For thesequence above, the cost of transforming algorithm to altruistic is(3 · cost(copy)) + cost(replace) + cost(delete) + (4 · cost(insert)) + cost(twiddle) + cost(kill).a.
Given two sequences x[1 m] and y[1 n] and set of transformation-operation costs,the edit distance from x to y is the cost of the least expensive operation sequence thattransforms x to y. Describe a dynamic-programming algorithm that finds the editdistance from x[1 m] to y[1 n] and prints an optimal operation sequence. Analyzethe running time and space requirements of your algorithm.The edit-distance problem is a generalization of the problem of aligning two DNA sequences(see, for example, Setubal and Meidanis [272, Section 3.2]). There are several methods formeasuring the similarity of two DNA sequences by aligning them.
One such method to aligntwo sequences x and y consists of inserting spaces at arbitrary locations in the two sequences(including at either end) so that the resulting sequences x′ and y′ have the same length but donot have a space in the same position (i.e., for no position j are both x′[j] and y′[j] a space.)Then we assign a "score" to each position. Position j receives a score as follows:•••+1 if x′[j] = y′[j] and neither is a space,-1 if x′[j] ≠ y′[j] and neither is a space,-2 if either x′[j] or y′[j] is a space.The score for the alignment is the sum of the scores of the individual positions.
For example,given the sequences x = GATCGGCAT and y = CAATGTGAATC, one alignment isG ATCG GCATCAAT GTGAATC-*++*+*+-++*A + under a position indicates a score of +1 for that position, a - indicates a score of -1, and a⋆ indicates a score of -2, so that this alignment has a total score of 6 · 1 - 2 · 1 - 4 · 2 _ -4.b. Explain how to cast the problem of finding an optimal alignment as an edit distanceproblem using a subset of the transformation operations copy, replace, delete, insert,twiddle, and kill.Problems 15-4: Planning a company partyProfessor Stewart is consulting for the president of a corporation that is planning a companyparty. The company has a hierarchical structure; that is, the supervisor relation forms a treerooted at the president.
The personnel office has ranked each employee with a convivialityrating, which is a real number. In order to make the party fun for all attendees, the presidentdoes not want both an employee and his or her immediate supervisor to attend.Professor Stewart is given the tree that describes the structure of the corporation, using theleft-child, right-sibling representation described in Section 10.4. Each node of the tree holds,in addition to the pointers, the name of an employee and that employee's conviviality ranking.Describe an algorithm to make up a guest list that maximizes the sum of the convivialityratings of the guests. Analyze the running time of your algorithm.Problems 15-5: Viterbi algorithmWe can use dynamic programming on a directed graph G = (V, E) for speech recognition.Each edge (u, v) E is labeled with a sound σ(u, v) from a finite set Σ of sounds.
The labeledgraph is a formal model of a person speaking a restricted language. Each path in the graphstarting from a distinguished vertex v0 V corresponds to a possible sequence of soundsproduced by the model. The label of a directed path is defined to be the concatenation of thelabels of the edges on that path.a. Describe an efficient algorithm that, given an edge-labeled graph G with distinguishedvertex v0 and a sequence s = σ1, σ2, ..., σk of characters from Σ, returns a path in Gthat begins at v0 and has s as its label, if any such path exists. Otherwise, the algorithmshould return NO-SUCH-PATH. Analyze the running time of your algorithm.
(Hint:You may find concepts from Chapter 22 useful.)Now, suppose that every edge (u, v) E has also been given an associated nonnegativeprobability p(u, v) of traversing the edge (u, v) from vertex u and thus producing thecorresponding sound. The sum of the probabilities of the edges leaving any vertex equals 1.The probability of a path is defined to be the product of the probabilities of its edges. We canview the probability of a path beginning at v0 as the probability that a "random walk"beginning at v0 will follow the specified path, where the choice of which edge to take at avertex u is made probabilistically according to the probabilities of the available edges leavingu.b. Extend your answer to part (a) so that if a path is returned, it is a most probable pathstarting at v0 and having label s. Analyze the running time of your algorithm.Problems 15-6: Moving on a checkerboardSuppose that you are given an n × n checkerboard and a checker.
You must move the checkerfrom the bottom edge of the board to the top edge of the board according to the followingrule. At each step you may move the checker to one of three squares:1. the square immediately above,2. the square that is one up and one to the left (but only if the checker is not already inthe leftmost column),3. the square that is one up and one to the right (but only if the checker is not already inthe rightmost column).Each time you move from square x to square y, you receive p(x, y) dollars. You are given p(x,y) for all pairs (x, y) for which a move from x to y is legal.
Do not assume that p(x, y) ispositive.Give an algorithm that figures out the set of moves that will move the checker fromsomewhere along the bottom edge to somewhere along the top edge while gathering as manydollars as possible. Your algorithm is free to pick any square along the bottom edge as astarting point and any square along the top edge as a destination in order to maximize thenumber of dollars gathered along the way. What is the running time of your algorithm?Problems 15-7: Scheduling to maximize profitSuppose you have one machine and a set of n jobs a1, a2, ..., an to process on that machine.Each job aj has a processing time tj, a profit pj, and a deadline dj. The machine can processonly one job at a time, and job aj must run uninterruptedly for tj consecutive time units. If jobaj is completed by its deadline dj, you receive a profit pj, but if it is completed after itsdeadline, you receive a profit of 0.
Give an algorithm to find the schedule that obtains themaximum amount of profit, assuming that all processing times are integers between 1 and n.What is the running time of your algorithm?[5]If the subject of the text is edible mushrooms, we might want "mycophagist" to appear nearthe root.Chapter notesR. Bellman began the systematic study of dynamic programming in 1955. The word"programming," both here and in linear programming, refers to the use of a tabular solutionmethod.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
