Your local newspaper started publishing puzzles of the following form: Parenthesize 6+0.6 to maximize the outcome....

  

Transcribed Image Text:

Your local newspaper started publishing puzzles of the following form: Parenthesize 6+0.6 to maximize the outcome. Wrong answer: 6+(0-6)=6+0= 6. Right answer: (6+0) 66.636. . Parenthesize 0.1.0.1+0.1 to maximize the outcome. Wrong answer: 0.1 (0.1 +0.1) Right answer: (0.1 0.1) + 0.1 0.1 0.2 = 0.02. 0.01 +0.1 = 0.11. To save yourself from tedium, but still impress your friends, you decide to implement an algorithm to solve these puzzles. The input to your algorithm is a sequence 1, 01, 2, 02, ., In, On, Xn+1 consisting of n + 1 non-negative real numbers 1,1,...,xn+1 and n operators 01,02,..., On Each operator o; is either addition (+) or multiplication (). (If it helps, you can view the input given to you as two separate arrays X[1..(n+1)] and O[1..n]). (a) Prove that the above problem exhibits optimal substructure. (b) Design a recursive backtracking (brute-force) algorithm that computes the maximum outcome for a given input of numbers and operators. Don't worry about making it fast for this part. (c) Modify your pseudocode in part (b) to use memoization. Write down the modified pseudocode. (d) Design a polynomial-time bottom-up dynamic programming algorithm for finding the optimal (maximum- outcome) parenthesization of the given expression, write down its pseudocode and analyze the running time. Argue why your choice of the array and the order in which you fill in the values is the correct one. (e) What additional information do you need to output actual parenthesization and not just the value of the outcome? Can you modify your algorithm to return the actual parent hesization? Your local newspaper started publishing puzzles of the following form: Parenthesize 6+0.6 to maximize the outcome. Wrong answer: 6+(0-6)=6+0= 6. Right answer: (6+0) 66.636. . Parenthesize 0.1.0.1+0.1 to maximize the outcome. Wrong answer: 0.1 (0.1 +0.1) Right answer: (0.1 0.1) + 0.1 0.1 0.2 = 0.02. 0.01 +0.1 = 0.11. To save yourself from tedium, but still impress your friends, you decide to implement an algorithm to solve these puzzles. The input to your algorithm is a sequence 1, 01, 2, 02, ., In, On, Xn+1 consisting of n + 1 non-negative real numbers 1,1,...,xn+1 and n operators 01,02,..., On Each operator o; is either addition (+) or multiplication (). (If it helps, you can view the input given to you as two separate arrays X[1..(n+1)] and O[1..n]). (a) Prove that the above problem exhibits optimal substructure. (b) Design a recursive backtracking (brute-force) algorithm that computes the maximum outcome for a given input of numbers and operators. Don't worry about making it fast for this part. (c) Modify your pseudocode in part (b) to use memoization. Write down the modified pseudocode. (d) Design a polynomial-time bottom-up dynamic programming algorithm for finding the optimal (maximum- outcome) parenthesization of the given expression, write down its pseudocode and analyze the running time. Argue why your choice of the array and the order in which you fill in the values is the correct one. (e) What additional information do you need to output actual parenthesization and not just the value of the outcome? Can you modify your algorithm to return the actual parent hesization?

Answer rating: 100% (QA)

a To prove that the above problem exhibits optimal substructure we need to show that the optimal solution to the problem can be obtained by combining the optimal solutions to its subproblems In this c... View the full answer