The document provides two new problems and solutions to add to chapter four exercises on string alignment and dynamic programming. Problem A asks to use hill-climbing to align two strings and compares it to an optimal dynamic programming solution. Problem B shows the Levenshtein distance between "weird" and its misspelling "wierd" is less than alternatives. It also rewrites an existing problem about calculating edit distances between strings using dynamic programming.
The document provides two new problems and solutions to add to chapter four exercises on string alignment and dynamic programming. Problem A asks to use hill-climbing to align two strings and compares it to an optimal dynamic programming solution. Problem B shows the Levenshtein distance between "weird" and its misspelling "wierd" is less than alternatives. It also rewrites an existing problem about calculating edit distances between strings using dynamic programming.
The document provides two new problems and solutions to add to chapter four exercises on string alignment and dynamic programming. Problem A asks to use hill-climbing to align two strings and compares it to an optimal dynamic programming solution. Problem B shows the Levenshtein distance between "weird" and its misspelling "wierd" is less than alternatives. It also rewrites an existing problem about calculating edit distances between strings using dynamic programming.
The document provides two new problems and solutions to add to chapter four exercises on string alignment and dynamic programming. Problem A asks to use hill-climbing to align two strings and compares it to an optimal dynamic programming solution. Problem B shows the Levenshtein distance between "weird" and its misspelling "wierd" is less than alternatives. It also rewrites an existing problem about calculating edit distances between strings using dynamic programming.
Download as DOC, PDF, TXT or read online from Scribd
Download as doc, pdf, or txt
You are on page 1/ 5
Chapter Four
Exercises Page 162
New Problems:
A. (To be placed before or after number 2)
Using the matrix shown in Figure 4.6, show the result of using hill-climbing to align the strings BAADDCABDDA with BBADCBA. Can hill-climbing produce the same result as an optimal solution using dynamic programming?
Solution: Hill-climbing works in the forward direction, and chooses the optimal solution at each step. Depending on how ties are broken, one possible solution is:
- B A A D D C A B D D A - 0 1 2 3 4 5 6 7 8 9 10 11 B 1 0 1 2 3 4 5 6 7 8 9 10 B 2 1 2 3 4 5 6 7 6 7 8 9 A 3 2 1 2 3 4 5 6 7 8 9 8 D 4 3 2 3 2 3 4 5 6 7 8 9 C 5 4 3 4 3 4 3 4 5 6 7 8 B 6 5 6 5 4 5 4 5 4 5 6 7 A 7 6 5 4 5 6 5 4 5 6 7 6
This solution corresponds to the alignment:
B– AADD CABDDA BBA– D – C – B– –A
Hill-climbing may produce the same result as the dynamic programming solution, but is not guaranteed to do so. B. (To be placed after number 3): Show that the word “weird” has a Levenshtein distance to its common misspelling, “wierd”, that is no longer than the alternatives “wired” and “wide”.
Solution: - W E I R D - 0 1 2 3 4 5 W 1 0 1 2 3 4 I 2 1 2 1 2 3 E 3 2 1 2 3 4 R 4 3 2 3 2 3 D 5 4 3 4 3 2
- W E I R D - 0 1 2 3 4 5 W 1 0 1 2 3 4 I 2 1 2 1 2 3 R 3 2 3 2 1 2 E 4 3 2 3 2 3 D 5 4 3 4 3 2
- W E I R D - 0 1 2 3 4 5 W 1 0 1 2 3 4 I 2 1 2 1 2 3 D 3 2 3 2 3 2 E 4 3 4 3 4 3
Rewritten Problems:
3. With the Levenshtein metric of Section 4.1.2, use dynamic programming to determine the minimum edit distance from source strings “maintenance” and “countenance” to “mountain”. Solution:
- M A I N T E N A N C E - 0 1 2 3 4 5 6 7 8 9 10 11 M 1 0 1 2 3 4 5 6 7 8 9 10 O 2 1 2 3 4 5 6 7 8 9 10 11 U 3 2 3 4 5 6 7 8 9 10 11 12 N 4 3 4 5 4 5 6 7 8 9 10 11 T 5 4 5 6 5 4 5 6 7 8 9 10 A 6 5 4 5 6 5 6 7 6 7 8 9 I 7 6 5 4 5 6 7 8 7 8 9 10 N 8 7 6 5 4 5 6 7 8 7 8 9
The minimum edit distance from “maintenance” to “mountain” is 9.
- C O U N T E N A N C E - 0 1 2 3 4 5 6 7 8 9 10 11 M 1 2 3 4 5 6 7 8 9 10 11 12 O 2 3 2 3 4 5 6 7 8 9 10 11 U 3 4 3 2 3 4 5 6 7 8 9 10 N 4 5 4 3 2 3 4 5 6 7 8 9 T 5 6 5 4 3 2 3 4 5 6 7 8 A 6 7 6 5 4 3 4 5 4 5 6 7 I 7 8 7 6 5 4 5 6 5 6 7 8 N 8 9 8 7 6 5 6 5 6 5 6 7
The minimum edit distance from “countenance” to “mountain” is 7.
13. Perform minimax on the following tree.
Solution:
14. Perform a left-to-right alpha-beta prune on the tree from Exercise 13. Perform a right-to-left prune on the same tree. Discuss why a different pruning occurs.
Solution:
Left-to-right: The tree is searched depth-first from left to right. The value of 5 at node B is reported, and β set to 5. Next the min of (0,5,9) is evaluated and 0 passed to E. C takes the value 3 which is the max of (0,3) and 3 is assigned to β, since 3 is less than 5. When the 7 is found at node G, the right subtree below D can be β-pruned because the value of D will be at least as large as 7, which is greater than the most recent β value of 3.
Right-to-left:
The tree is searched depth first, right to left. (0,5) are compared, and P is assigned 5. The β-value associated with node H is set to 5, so no subtree below H with a value greater than 5 need be considered. We look next at node N, which is 7. We could not prune N because we had to look at it to determine its value. Next, node S is searched, which gives a value of 3. Since this will potentially change the value of β at H, we have to search R, which gives us 7 at M and 5 at H. We set the α value at node D to 5 because we do not need to consider any min grandchild of D whose value is less than 5. D only has one other grandchild, and its value is 7, so the α associated with D is set to 7. The β value of the root node is set to 7, and no child of the root evaluating to more than 7 need to be considered further. The next node evaluated is F, which has a value of 3, and the α value associated with C is set to 3, and no node whose value is greater than 3 need be considered. However, L, K, and J have to be evaluated because L, and K both have values greater than 3. Thus 0 is assigned to E, and 3 is assigned to the β value associated with the root. The final node, B, cannot be pruned because although its value is greater than the last β value of the root, it has to be examined to determine this.
Immediate download Spreadsheet Modeling and Decision Analysis A Practical Introduction to Business Analytics 8th Edition Ragsdale Solutions Manual all chapters
Immediate download Spreadsheet Modeling and Decision Analysis A Practical Introduction to Business Analytics 8th Edition Ragsdale Solutions Manual all chapters
