Breaking a string A certain string-processing language

Longest simple path in a directed acyclic graph Suppose that we are given a directed acyclic graph G D .V; E/ with realvalued edge weights and two distinguished vertices s and t. Describe a dynamicprogramming approach for finding a longest weighted simple path from s to t. What does the subproblem graph look like? What is the efficiency of your algorithm?

Longest palindrome subsequence 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 efficient algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input character, your algorithm should return carac. What is the running time of your algorithm?

Bitonic euclidean traveling-salesman problem In the euclidean traveling-salesman problem, we are given a set of n points in the plane, and we wish to find the shortest closed tour that connects all n points. Figure 15.11(a) shows the solution to a 7-point problem. The general problem is NP-hard, and its solution is therefore believed to require more than polynomial time (see Chapter 34). J. L. Bentley has suggested that we simplify the problem by restricting our attention to bitonic tours, that is, tours that start at the leftmost point, go strictly rightward to the rightmost point, and then go strictly leftward back to the starting point. Figure 15.11(b) shows the shortest bitonic tour of the same 7 points. In this case, a polynomial-time algorithm is possible. Describe an O.n2/-time algorithm for determining an optimal bitonic tour. You may assume that no two points have the same x-coordinate and that all operations on real numbers take unit time. (Hint: Scan left to right, maintaining optimal possibilities for the two parts of the tour.)

Printing neatly Consider the problem of neatly printing a paragraph with a monospaced font (all characters having the same width) on a printer. The input text is a sequence of n 406 Chapter 15 Dynamic Programming words of lengths l1; l2;:::;ln, measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of M characters each. Our criterion of neatness is as follows. If a given line contains words i through j , where i j , and we leave exactly one space between words, the number of extra space characters at the end of the line is M j C i Pj kDi lk, which must be nonnegative so that the words fit on the line. We wish to minimize the sum, over all lines except the last, of the cubes of the numbers of extra space characters at the ends of lines. Give a dynamic-programming algorithm to print a paragraph of n words neatly on a printer. Analyze the running time and space requirements of your algorithm.

Edit distance In order to transform one source string of text x1 : : m to a target string y1 : : n, we can perform various transformation operations. Our goal is, given x and y, to produce a series of transformations that change x to y. We use an array assumed to be large enough to hold all the characters it will needto hold the intermediate results. Initially, is empty, and at termination, we should have j D yj for j D 1; 2; : : : ; n. We maintain current indices i into x and j into , and the operations are allowed to alter and these indices. Initially, i D j D 1. We are required to examine every character in x during the transformation, which means that at the end of the sequence of transformation operations, we must have i D m C 1. We may choose from among six transformation operations: Copy a character from x to by setting j D xi and then incrementing both i and j . This operation examines xi. Replace a character from x by another character c, by setting j D c, and then incrementing both i and j . This operation examines xi. Delete a character from x by incrementing i but leaving j alone. This operation examines xi. Insert the character c into by setting j D c and then incrementing j , but leaving i alone. This operation examines no characters of x. Twiddle (i.e., exchange) the next two characters by copying them from x to but in the opposite order; we do so by setting j D xi C 1 and j C 1 D xi and then setting i D i C 2 and j D j C 2. This operation examines xi and xi C 1. Kill the remainder of x by setting i D m C 1. This operation examines all characters in x that have not yet been examined. This operation, if performed, must be the final operation. Problems for Chapter 15 407 As an example, one way to transform the source string algorithm to the target string altruistic is to use the following sequence of operations, where the underlined characters are xi and j after the operation: Operation x initial strings algorithm copy algorithm a copy algorithm al replace by t algorithm alt delete algorithm alt copy algorithm altr insert u algorithm altru insert i algorithm altrui insert s algorithm altruis twiddle algorithm altruisti insert c algorithm altruistic kill algorithm altruistic Note that there are several other sequences of transformation operations that transform algorithm to altruistic. Each of the transformation operations has an associated cost. The cost of an operation depends on the specific application, but we assume that each operations cost is a constant that is known to us. We also assume that the individual costs of the copy and replace operations are less than the combined costs of the delete and insert operations; otherwise, the copy and replace operations would not be used. The cost of a given sequence of transformation operations is the sum of the costs of the individual operations in the sequence. For the sequence above, the cost of transforming algorithm to altruistic is .3 cost.copy// C cost.replace/ C cost.delete/ C .4 cost.insert// C cost.twiddle/ C cost.kill/ : a. Given two sequences x1 : : m and y1 : : n and set of transformation-operation costs, the edit distance from x to y is the cost of the least expensive operation sequence that transforms x to y. Describe a dynamic-programming algorithm that finds the edit distance from x1 : : m to y1 : : n and prints an optimal operation sequence. Analyze the running time and space requirements of your algorithm. The edit-distance problem generalizes the problem of aligning two DNA sequences (see, for example, Setubal and Meidanis [310, Section 3.2]). There are several methods for measuring the similarity of two DNA sequences by aligning them. One such method to align two sequences x and y consists of inserting spaces at 408 Chapter 15 Dynamic Programming arbitrary locations in the two sequences (including at either end) so that the resulting sequences x0 and y0 have the same length but do not have a space in the same position (i.e., for no position j are both x0 j and y0 j a space). Then we assign a score to each position. Position j receives a score as follows: C1 if x0 j D y0 j and neither is a space, 1 if x0 j y0 j and neither is a space, 2 if either x0 j or y0 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 D GATCGGCAT and y D CAATGTGAATC, one alignment is G ATCG GCAT CAAT GTGAATC -*++*+*+-++* A + under a position indicates a score of C1 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 D 4. b. Explain how to cast the problem of finding an optimal alignment as an edit distance problem using a subset of the transformation operations copy, replace, delete, insert, twiddle, and kill. 15-6 Plannin

Planning a company party Professor Stewart is consulting for the president of a corporation that is planning a company party. The company has a hierarchical structure; that is, the supervisor relation forms a tree rooted at the president. The personnel office has ranked each employee with a conviviality rating, which is a real number. In order to make the party fun for all attendees, the president does 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 the left-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 employees conviviality ranking. Describe an algorithm to make up a guest list that maximizes the sum of the conviviality ratings of the guests. Analyze the running time of your algorithm.

Viterbi algorithm We can use dynamic programming on a directed graph G D .V; E/ for speech recognition. Each edge .u; / 2 E is labeled with a sound .u; / from a fi- nite set of sounds. The labeled graph is a formal model of a person speaking Problems for Chapter 15 409 a restricted language. Each path in the graph starting from a distinguished vertex 0 2 V corresponds to a possible sequence of sounds produced by the model. We define the label of a directed path to be the concatenation of the labels of the edges on that path. a. Describe an efficient algorithm that, given an edge-labeled graph G with distinguished vertex 0 and a sequence s D h 1; 2;:::; ki of sounds from , returns a path in G that begins at 0 and has s as its label, if any such path exists. Otherwise, the algorithm should 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; / 2 E has an associated nonnegative probability p.u; / of traversing the edge .u; / from vertex u and thus producing the corresponding 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 can view the probability of a path beginning at 0 as the probability that a random walk beginning at 0 will follow the specified path, where we randomly choose which edge to take leaving a vertex u according to the probabilities of the available edges leaving u. b. Extend your answer to part (a) so that if a path is returned, it is a most probable path starting at 0 and having label s. Analyze the running time of your algorithm. 15-8 Im

Image compression by seam carving We are given a color picture consisting of an m n array A1 : : m; 1 : : n of pixels, where each pixel specifies a triple of red, green, and blue (RGB) intensities. Suppose that we wish to compress this picture slightly. Specifically, we wish to remove one pixel from each of the m rows, so that the whole picture becomes one pixel narrower. To avoid disturbing visual effects, however, we require that the pixels removed in two adjacent rows be in the same or adjacent columns; the pixels removed form a seam from the top row to the bottom row where successive pixels in the seam are adjacent vertically or diagonally. a. Show that the number of such possible seams grows at least exponentially in m, assuming that n>1. b. Suppose now that along with each pixel Ai; j , we have calculated a realvalued disruption measure di; j , indicating how disruptive it would be to remove pixel Ai; j . Intuitively, the lower a pixels disruption measure, the more similar the pixel is to its neighbors. Suppose further that we define the disruption measure of a seam to be the sum of the disruption measures of its pixels. Dynamic Programming Give an algorithm to find a seam with the lowest disruption measure. How efficient is your algorithm?

Breaking a string A certain string-processing language allows a programmer to break a string into two pieces. Because this operation copies the string, it costs n time units to break a string of n characters into two pieces. Suppose a programmer wants to break a string into many pieces. The order in which the breaks occur can affect the total amount of time used. For example, suppose that the programmer wants to break a 20-character string after characters 2, 8, and 10 (numbering the characters in ascending order from the left-hand end, starting from 1). If she programs the breaks to occur in left-to-right order, then the first break costs 20 time units, the second break costs 18 time units (breaking the string from characters 3 to 20 at character 8), and the third break costs 12 time units, totaling 50 time units. If she programs the breaks to occur in right-to-left order, however, then the first break costs 20 time units, the second break costs 10 time units, and the third break costs 8 time units, totaling 38 time units. In yet another order, she could break first at 8 (costing 20), then break the left piece at 2 (costing 8), and finally the right piece at 10 (costing 12), for a total cost of 40. Design an algorithm that, given the numbers of characters after which to break, determines a least-cost way to sequence those breaks. More formally, given a string S with n characters and an array L1 : : m containing the break points, compute the lowest cost for a sequence of breaks, along with a sequence of breaks that achieves this cost.

Planning an investment strategy Your knowledge of algorithms helps you obtain an exciting job with the Acme Computer Company, along with a $10,000 signing bonus. You decide to invest this money with the goal of maximizing your return at the end of 10 years. You decide to use the Amalgamated Investment Company to manage your investments. Amalgamated Investments requires you to observe the following rules. It offers n different investments, numbered 1 through n. In each year j , investment i provides a return rate of rij . In other words, if you invest d dollars in investment i in year j , then at the end of year j , you have drij dollars. The return rates are guaranteed, that is, you are given all the return rates for the next 10 years for each investment. You make investment decisions only once per year. At the end of each year, you can leave the money made in the previous year in the same investments, or you can shift money to other investments, by either shifting money between existing investments or moving money to a new investement. If you do not move your money between two consecutive years, you pay a fee of f1 dollars, whereas if you switch your money, you pay a fee of f2 dollars, where f2 > f1. Problems for Chapter 15 411 a. The problem, as stated, allows you to invest your money in multiple investments in each year. Prove that there exists an optimal investment strategy that, in each year, puts all the money into a single investment. (Recall that an optimal investment strategy maximizes the amount of money after 10 years and is not concerned with any other objectives, such as minimizing risk.) b. Prove that the problem of planning your optimal investment strategy exhibits optimal substructure. c. Design an algorithm that plans your optimal investment strategy. What is the running time of your algorithm? d. Suppose that Amalgamated Investments imposed the additional restriction that, at any point, you can have no more than $15,000 in any one investment. Show that the problem of maximizing your income at the end of 10 years no longer exhibits optimal substructure.

Inventory Planning The Rinky Dink Company makes machines that resurface ice rinks. The demand for such products varies from month to month, and so the company needs to develop a strategy to plan its manufacturing given the fluctuating, but predictable, demand. The company wishes to design a plan for the next months. For each month , the company knows the demand , that is, the number of machines that it will sell. Let be the total demand over the next months. The company keeps a full-time staff who provide labor to manufacture up to m machines per month. If the company needs to make more than machines in a given month, it can hire additional, part-time labor, at a cost that works out to dollars per machine. Furthermore, if, at the end of a month, the company is holding any unsold machines, it must pay inventory costs. The cost for holding machines is given as a function for , where for and for and for . Give an algorithm that calculates a plan for the company that minimizes its costs while fulfilling all the demand. The running time should be polynomial in and .

Signing free-agent baseball players Suppose that you are the general manager for a major-league baseball team. During the off-season, you need to sign some free-agent players for your team. The team owner has given you a budget of $X to spend on free agents. You are allowed to spend less than $X altogether, but the owner will fire you if you spend any more than $X. You are considering N different positions, and for each position, P free-agent players who play that position are available.8 Because you do not want to overload your roster with too many players at any position, for each position you may sign at most one free agent who plays that position. (If you do not sign any players at a particular position, then you plan to stick with the players you already have at that position.) To determine how valuable a player is going to be, you decide to use a sabermetric statistic9 known as VORP, or value over replacement player. A player with a higher VORP is more valuable than a player with a lower VORP. A player with a higher VORP is not necessarily more expensive to sign than a player with a lower VORP, because factors other than a players value determine how much it costs to sign him. For each available free-agent player, you have three pieces of information: the players position, the amount of money it will cost to sign the player, and the players VORP. Devise an algorithm that maximizes the total VORP of the players you sign while spending no more than $X altogether. You may assume that each player signs for a multiple of $100,000. Your algorithm should output the total VORP of the players you sign, the total amount of money you spend, and a list of which players you sign. Analyze the running time and space requirement of your algorithm.