Reference no: EM132700846

For all algorithms design problems, describe your algorithm in words, then give a (concise and human- readable) pseudo-code.

1. Longest streak of CO2 increase

Suppose that you are working with a scientist studying how the levels of CO2 in the atmosphere change over time. She obtained the data showing the level of CO2 in the atmosphere every year for a long period of time, and would like to find a block of consecutive years during which the increase of CO2 was maximal. To help with algorithm design, she converted the data into a list of numbers showing relative increase or decrease of CO2 this year in comparison to the previous year, and now all that is left is to design an algorithm to solve this problem (as fast as possible).

For example, suppose that the sequence of relative increases/decreases is f63; -59; 41; 11; -13; 53;
-35; 11g.Then the largest increase happens over years 3 to 6, with 41+11-13+53=92.

a) Design a brute-force Θ(n2) algorithm to solve this problem. Make sure your description and pseudo-code are concise and clean, and include an explanation why this algorithm works.
b) Now, design a Θ(n log n) divide-and-conquer algorithm for this problem.
i. Describe your algorithm in words
ii. Give (concise) pseudo-code.
iii. Give a recurrence for its running time, and explain why this recurrence gives you Θ(n log n).
iv. Explain why your algorithm computes an optimal solution.
c) Finally, give a Θ(n) dynamic programming algorithm solving this problem.
i. First, describe your algorithm in words.
ii. Give the definition of an array A that you will use to solve the problem. How can you get the amount of the maximal increase in CO2 over all blocks of consecutive years from this array A?
iii. Give a recurrence to compute elements of A, including initialization.
iv. Show the filled array for the example above produced by your algorithm.
v. Give pseudo-code for a dynamic programming algorithm that finds the amount of the maximal increase in CO2 over all blocks of consecutive years.
vi. Explain (in text and pseudo-code) how to recover the actual block of years from the array computed while finding the maximal increase in CO2. You can add information to the array when computing it, if you wish.
vii. Explain why your algorithm works and why it runs in linear time

2. Farmers barter

You are trying to facilitate barter among farmers at a market using your algorithm design skills. The problem is as follows: suppose one farmer brings a list of items to the market, with each item having a certain price (eg, a bunch of squashes), and wants to barter with another farmer for an item they have available (eg, a baby goat), where that second farmer has a selection of baby goats of different prices. To make the barter fair, the sum of prices of the squashes the first farmer gives to the second should exactly equal to the price of the baby goat she gets in exchange.

For example, the first farmer might have brought squashes costing 10; 12; 15; 15; 21; 24; 33, and the goats cost 20; 25; 30; 32. Then she can get the second goat with the first and third squashes, or the third goat with third and fourth squashes, but she cannot get the first or the fourth goats, since none of subsets of squashes cost 20 or 32.

Here, you will need to design a dynamic programming algorithm that takes as an input the list of prices of items the first farmer brought to barter (let's just call them squashes), and list of prices of items out of which she would like to buy one (let's call them goats), and outputs a list of goats that can be bartered, and, for each goat, the list of squashes that can be bartered for it. Remember that she only wants one goat, just choosing which one she can get, so lists of squashes for different goats do not have to be disjoint.

a) Describe your algorithm in words.
b) Give the definition of an array A that you will use to solve the problem. How can you get the list of goats each of which the first farmer can buy with her squashes from this array A? How can you check if there is no solution (that is, that she cannot find a set of squashes costing as much as any of the goats in the list)?
c) Give a recurrence to compute elements of A, including initialization.
d) Show the filled array as produced by your algorithm for the example above.
e) Give pseudo-code for a dynamic programming algorithm that finds which goats can be bartered for a (subset of) given squashes.
f) Explain (in text and pseudo-code) how, given a specific goat which can be bartered, to recover a set of squashes that sum up to its price from the array A. You can add information to the array when computing it, if you wish.
g) Finally, implement your algorithm. It should take as an input a comma-separated list of squash prices, followed by a newline, followed by a comma-separated list of goat prices, and output first the list of goats that can be bartered given this list of squashes, and then, for each goat that can be bartered, a corresponding list of squashes in the same order as in the input.