Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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

image text in transcribed

Your local newspaper started publishing puzzles of the following form: Parenthesize 6 +0.6 to maximize the outcome. Parenthesize 0.1-0.1 0.1 to maximize the outcome. Wrong answer: 6 + (0-6) = 6 + 0 = 6. Right answer: (6 0) . 6 = 6-6 36. Wrong answer: 0.1 . (0.1 + 0.1) = 0.1 , 0.2 0.02. Right answer: (0.1-0.1) 0.1 = 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 consisting of n+ 1 non-negative real numbers z1,x!, ,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 011 ..n]). (a) (10 pts) Prove that the above problem exhibits optimal substructure. (b) (15 pts) Design a recursive 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) (5 pts) Modify your pseudocode in part (b) to use memoization. Write down the modified pseudocode. (d) (15 pts) 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 alues is the correct one. Your local newspaper started publishing puzzles of the following form: Parenthesize 6 +0.6 to maximize the outcome. Parenthesize 0.1-0.1 0.1 to maximize the outcome. Wrong answer: 6 + (0-6) = 6 + 0 = 6. Right answer: (6 0) . 6 = 6-6 36. Wrong answer: 0.1 . (0.1 + 0.1) = 0.1 , 0.2 0.02. Right answer: (0.1-0.1) 0.1 = 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 consisting of n+ 1 non-negative real numbers z1,x!, ,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 011 ..n]). (a) (10 pts) Prove that the above problem exhibits optimal substructure. (b) (15 pts) Design a recursive 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) (5 pts) Modify your pseudocode in part (b) to use memoization. Write down the modified pseudocode. (d) (15 pts) 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 alues is the correct one

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

More Books

Students also viewed these Databases questions

Question

RP-2 What is the best way to predict a persons future behavior?

Answered: 1 week ago