Your local newspaper started publishing puzzles of the following form: Parenthesize 6+0.6 to maximize the outcome....
Fantastic news! We've Found the answer you've been seeking!
Question:
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?
Expert Answer:
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
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these programming questions
-
"internet radios" for streaming audio, and personal video recorders and players. Describe design and evaluation processes that could be used by a start-up company to improve the usability of such...
-
CANMNMM January of this year. (a) Each item will be held in a record. Describe all the data structures that must refer to these records to implement the required functionality. Describe all the...
-
On January 2, 2016, Allen Company purchased a machine for $70,000. This machine has a five-year useful life, a residual value of $10,000, and it is depreciated using the straight-line method for...
-
Tsunamis are fast-moving waves often generated by underwater earthquakes. In the deep ocean their amplitude is barely noticeable, but upon reaching shore, they can rise up to the astonishing height...
-
A worker slowly moves a 50-kg crate to the left along a loading dock by applying a force P at corner B as shown. Knowing that the crate starts to tip about the edge E of the loading dock when a = 200...
-
The plaintiff, Thelma Agnes Smith, lived with the defendant out of wedlock for several years. When the relationship ended, she sued the defendant, seeking to enforce two written agreements with him...
-
Comparing Income with Cash Flow (A Challenging Problem) Huang Trucking Company was organized on January 1, 2011. At the end of the first quarter (three months) of operations, the owner prepared a...
-
Research articles on Online Analytic Processing (OLAP) and Online Transaction Processing (OLTP). Next, compare and contrast the key similarities and differences between Online Analytical Processing...
-
This calculation considers the fixed and variable costs, along with the price of the goods or services sold, in order to determine how many of those goods and services need to be sold in order to...
-
Galaxy Company has following balances from previous month-May: Cash: $900.000 debit balance, Bank: $800.000 debit balance, Goods: $400.000 debit balance A) General Journal Entries (85 pts) Galaxy...
-
Two particles have positions at time t given by s1=4t-t 2 and s2 = 5t 2 -t 3 . when the acceleration of the two particles are equal, find the positions and velocities of both particles.
-
What is the frequency of light with a wavelength of 756nm?
-
Q1. Identify and explain the major factors motivating firms' international location decision strategies (e.g., manufacturing internationally) in many countries such as the UAE. Q2. Identify and...
-
A chunk of nickel weighing 19.0 grams and originally at 98.12 C is dropped into an insulated cup containing 83.6 grams of water at 21.62 C. Assuming that all of the heat is transferred to the water,...
-
1. What are the positive and negative aspects of having goals in our lives? 2. What is the "sweet spot" the instructor was mentioning between and organization's focus and a personal focus (Behavior...
-
Write out the formula for the total costs of carrying and ordering inventory, and then use the formula to derive the EOQ model. Andria Mullins, financial manager of Webster Electronics, has been...
-
Kathy Kennedy (age 44) is a single taxpayer and she lives at 212 North Pine Way, Payson, AZ 85541. Her Social Security number is 467-98-9784. Kathy's earnings and income tax withholding as the...
-
For each of the following cases, indicate the filing status for the taxpayer(s) for 2012 using the following legend: A - Single B - Married, filing a joint return C - Married, filing separate returns...
-
Sally hires a maid to work in her home for $250 per month. The maid is 25 years old and not related to Sally. During 2012, the maid worked 10 months for Sally. a. What is the amount of Social...
-
Whittier Construction Co. had followed the practice of expensing all materials assigned to a construction job without recognizing any residual inventory. On December 31, 2015, it was determined that...
-
Prior to 2015, Heberling Inc. excluded manufacturing overhead costs from work in process and finished goods inventory. These costs have been expensed as incurred. In 2015, the company decided to...
-
What is the difference between a future taxable amount and a future deductible amount? When is it not appropriate to recognize a portion or all of a deferred tax asset?
Study smarter with the SolutionInn App