Assignment 3 Solution

    • \In Hartford, Hereford, and Hampshire...

... hurricanes hardly ever happen." Unfortunately, though, hurricanes do hap-pen elsewhere. As such, you’ve been formally requested by the British prime minister, Sir Henry Higgins, to lead the project on setting up emergency bunkers throughout England in hopes of reducing casualties during a hurricane. In par-ticular, inhabitants of every town in England should be able to reach a bunker in a reasonable amount of time.

One proposal is to build a bunker in each and every town, thus eliminating travel time and ensuring safety for all. However, due to deployment and maintenance costs, this solution turns out to be outside of the allocated budget. A much more cost e ective strategy is to build a single bunker at a reasonable distance from all the towns, but that will lead to long travel times and congestion along

1





the roads, which is expected to increase casualties.

Instead, you propose a happy medium: build a set of bunkers such that a town either has a bunker built in it, or is directly connected to a town which has a bunker. This reduces the number of bunkers needed, while still allowing all inhabitants ample time to get to safety. Satis ed with your proposition, PM Higgins allocates funds for this project (code-named Pygmalion) and asks you to come up with a method to solve it.

You formally set up the problem, PYGMALION, as follows: Given an undirected graph G, where nodes represent towns and edges represent roads, and given a number k, is there a way to build k bunkers at k di erent towns so that every town either has its own bunker, or is connected by a (direct) road to a town that does have a bunker?

Thinking about a solution, you sadly realize what you’ve gotten yourself into: Show that PYGMALION is NP-Complete. Follow all the steps we have outlined in class for a complete proof.

Note: Props to anyone who caught all the literary references above. If you haven’t, you may need to brush up on your English literature. ,
    • Programming

Amrita has recently earned $10,000 in cash by gambling (lucky her!). She wants to buy a brand new car. However, she doesn’t have enough money yet and of course she is wise enough to not take the risk of gambling again. She usually takes the bus home while dreaming of her own car. \My dark gray car, you are the most beautiful car in the world", she imagines.

One day, while day-dreaming, her eyes fell on an advertisement which changed her life:


Do you want money to buy a car? or a home?


Join us today. Tomorrow is too late!


Pool-o-Pale Investment Co. Visit www.pool-o-pale.com.


She visits the website as soon as she gets home and reads the rules and regulations. She nds that she has to invest her money. They will pay her daily interest, a typical banking approach. She then nds a very appealing rule:


The interest rates are known in advance!


For example, tomorrow’s interest rate is 3.5 %. This means that tomorrow, the bank will pay Amrita 0:035×10000. The interest rate on the day after tomorrow is −2:1%, which means that they will claim 0:021 × 10000 of her money on that day. Amrita gets excited about this: she can invest on the days with positive interest rates only! \That’s great!", she thought, feeling that she was closer than ever to buying the car. But then, she goes on to read the next rule:


Every person can join the Pool-o-Pale once!



2





\What a bad rule!" she whispered disappointedly. This means that she has to join the plan on one given day, and remain so till some later day. Then, she will earn money at the rate equal to the summation of the interest rates on those days. \How can I earn as much money as possible? I wish I knew of an algorithm that nds the best investment period for me", she thinks. That night she slept while driving her dark gray car in her dreams.

Let’s help Amrita buy a car! Tomorrow morning, she is going to a branch of Pool-o-Pale. The manager will give her a spreadsheet containing the xed interest rates from now until some days later. She has less than ten seconds to decide the interval she is going to invest within. You are going to help her nd an e cient algorithm to accomplish this. You can, because you know how to design and analyze e cient algorithms! ,

Suppose the manager will give her a text le containing on its rst line, n, the total number of days in the plan. Then, at line i she will receive a (positive or negative) real number indicating the daily interest rate, say ai. If you really want to help her, you have to nd the indices j and k such that ∑j≤i≤k ai is maximum. Assume that there exists at least one day where the interest rate is positive (otherwise, there is no reason why Amrita should invest). Remember you have only ten seconds.

You, as an algorithm expert, should try and analyze the following proposals:

    • A brute-force approach for this problem seems very naive. You can design a faster algorithm. Believe in yourself! Implement a divide-and-conquer approach by splitting the array into two halves. The best solution will either be:

{ fully contained in the rst half { fully contained in the second half

{ such that its start point is in the rst half and its end point in the second half

The rst two cases are handled recursively. The third one is a linear search.

    • Secondly, you will implement a more clever solution by dynamic program-ming: Assume that the days are indexed by the set I = {1; :::; n}. Let B(j) denote the maximum sum of interest rates that can be obtained if j ∈ I is Amrita’s last day of investment. Then, it is easy to see that B(j) can be computed using the following recurrence relation:
( ) = œ max{B(j − 1) + aj ; 0}
j
=
0
B j
0





otherwise




In words, if j is Amrita’s last day of investment, the maximum interest rate she can obtain up to j is either: the maximum interest rate she can obtain up to j − 1, plus that of the j-th day (if B(j − 1) + aj ≥ 0); or zero (if B(j − 1) + aj < 0, i.e. there is no investment interval ending on day j that is pro table).

3




You can easily (and e ciently) compute B(j); ∀j ∈ I using a bottom-up approach. Once you have computed all the necessary B(j ) values, you can solve Amrita’s problem by returning the the best i and j values (Hint: the best i and j correspond to the B(j) that is maximum among all j ∈ I).

You will help Amrita by implementing the two aforementioned algorithms (divide-and-conquer and dynamic programming). Your algorithms should take inputs and generate outputs as follows.

Input: The rst line contains two numbers. The rst one, n, is the number of days. The second one, k, is the number of instances of the problem you should solve. Then, the next k lines contain n comma separated values. The input les are named <n>.txt, e.g. 7.txt and have the form:

7,3

-1.5,3.4,-3.1,1.7,2.7,-4.8,3.4

-1.2,3.8,-6.1,9.7,2.8,-5.8,1.4

-3.5,6.4,-3.1,1.7,1.7,-1.8,3.2

Output: For each algorithm and each input le there should be an output le with k lines. Each line has four numbers. The rst one is the maximum value of interest rate Amrita will receive. The next two numbers are the indices of the the start and end days of optimal investment, and are in the range [1; n]. The last value is the running time of the corresponding algorithm in milliseconds. Values are separated by commas, and non-integer values are output with two decimal digits.

4.78,2,6,1554.21

...

...

Your should submit the output for both algorithms corresponding to the input les provided. Your outputs should be named as

<GTusername>_output_<algorithm>_<n>.txt

where <algorithm> should be either dc (for divide and conquer) or dp (for dy-namic programming). Put all output les in a folder named output.

Sample data for debugging: We provide a sample input  le with (n =

10; k = 10) in 10.txt, and the corresponding sample output le in drobinson67_output_dc_10.txt. If your algorithms are correct, they will have the same values for the rst three
columns of the sample output le. Note that you should not submit your output le for this sample dataset.

Deliverables: You should create a zip le for the programming portion of this assignment named, <GTusername>_HW3_program.zip, that includes the following:

    • Source for the two algorithms, well structured and commented. Similar to Assignment 1, you are allowed to use Python, Java, C, or C++.



4





    • A README le explaining how to run your codes. If you use Java, C, or C++, please also include the command(s) you use to compile your code (we should be able to compile (if necessary) and run your code and see the output les generated).

    • A folder named output containing the corresponding output of the input les provided in. The output should be in the format described in the \Output" section above.

You should also create a report and submit it as a PDF titled <GTusername>_HW3_report.pdf (e.g. drobinson67_HW3_report.pdf) on t-square. The report should include:

    • A description of your divide and conquer algorithm.

    • A description of your dynamic programming algorithm.

    • Time and space complexity analysis of both algorithms.

    • A single graph with two lines that shows how the average running time of your algorithms grows with n. For each input size, n, average the running time over the k instances in the input le for that value of n.

    • Observations about your empirical results that tie back into your time and space complexity analysis.

    • Discussion on how the two algorithms compare with each other in terms of the complexity and empirical performance.
































5