Assignment 1 Solution

Please upload a PDF with solutions to all the problems. If you handwrite the solutions rst, please make sure all answers are legible; no credit will be given to illegible answers.

    • Greedy - The Great Ice Cream Sale

Amrita’s Amazing Ice Cream shop is the talk of Georgia Tech. It produces the same n delicious avors freshly every day, and never resells old ice cream made on previous days. In order to get rid of the extra ice cream at the end of each day, Amrita’s Amazing Ice Cream has a special deal at closing time. They sell 1 gallon buckets of ice cream for a fraction of the usual price, packed with your choice of leftover ice cream. You can choose as many avors as you like that can t in the bucket; however, because Amrita’s wants to get rid of their ice cream as quickly as possible, their only stipulation is that once you choose a avor, you need to take it all (or as much as you can until your bucket is full).

Being a poor college student, you love quality ice cream as much as the next per-son, but can only a ord to buy Amrita’s ice cream with the special deal. Your goal is to come home with the best ice cream bucket every time, i.e. packed to maximize the total likeability score L of all its avors. The total score L is the sum of each individual ice cream’s score si, which you decide when you see how much ice cream of each avor is left for the day. This score si assumes you are getting the full quantity di of the ice cream avor i for that day; if you only receive a fraction of the ice cream avor i for that day, you only receive the proportional fraction of the score. For example, consider that the Ice Cream Shop has 3 avors with leftover amounts of d1 = 1; d2 = 0:5; d3 = 0:25 gallons, and your scores for them are s1; s2; s3. If you pick avor 1 to ll your bucket, this gives you a score of L = s1. If you decide to pick avor 2 rst, and ll the other half gallon with ice cream 1, this would give you a score of L = s2

    • s21 (you only get half the score of 1 because you only get half the amount of 1). If you rst decide to get ice cream 3 with its quantity of a fourth gallon (d3 = 0:25), then avor 2, then avor 1, then you will be getting all of avor 3,

all of    avor 2, and a fourth of    avor 1’s amount; your score is thus L = s3 + s2
    • s41 .


The amount of each ice cream di left at the end of the day changes daily, and


1





so your optimal ice cream bucket may also change. Assume your scores si are already calibrated to the amount di in question. Hence, instead of spending time every day to gure out your optimal ice cream bucket, you’ve decided to design an algorithm to help you out. Give an e cient algorithm to decide on the best combination of ice cream to get to maximize its score L. Prove that your algorithm does indeed yield an optimal bucket. (For the sake of analysis, you may assume that each avor’s amount can be measured as an integer number of ounces.)



    • Dynamic Programming: George Learns Algo-rithms

George P. Burdell has been taking the algorithms course at Tech every year since the College of Computing opened in 1964. As he looks at his transcripts over the decades, he wonders if he has been getting the hang of the material. The di culty of the course varied based on which instructor taught it and how much time George spent at Georgia Tech football games, so naturally his nal scores uctuated from year to year. He decides the best way to measure his progress is to look at the sequence of nal scores he earned (thankfully they are all positive and 100) and nd the longest subsequence of scores over which his grade strictly improved. He looks at his grades from 1980-1989:

f82; 77; 65; 89; 83; 68; 88; 71; 91; 90g

George does not want to restrict himself to only contiguous years, since then it looks like he is never able to improve his performance for longer than 2 years (f65; 89g or f68; 88g or f71; 91g). If he allows himself to leave out whatever years he likes, he could see his grade improving over the following 3 scores: f77; 89; 91g. Or better yet, the following 4 scores: f77; 83; 88; 91g.

Feeling better about himself already, George de nes a subsequence to be the original sequence with some (or all) of the elements removed. Now, he enlists the help of one his clever classmates from this year’s algorithms class (you) to nd his longest subsequence of improving grades.

    1. George is not convinced that his problem can be solved any way besides a brute force search through all 2n possible subsequences (where n is the number of times George took algorithms). Prove this problem has optimal substructure to show George there may be a better approach.

    2. Write down a recurrence relation for this problem.

    3. Design a bottom up DP algorithm to solve the problem. Include the time and space complexity of this algorithm to conclusively show George that your algorithm is better than an exhaustive search.








2





    • Dynamic Programming: Most Mysterious Man-sion


You are playing a game in which you must manage a team of 2 adventurers as they travel through a cursed mansion lled with monsters. The explorers accumulate stress every time they encounter a monster, starting with 0 stress at the beginning of the excursion. Each of them can handle at most S units of stress. Each monster causes an even amount of stress si (in other words: si=2 will be an integer) and defeating it yields reward ri. In order to defeat a monster, one of the 2 adventurers must step up and ght it, causing their own stress level to increase by si, but earning reward ri for the team. (Note, if the ght would cause the adventurer to exceed their stress threshold, they cannot defeat the monster.) Alternatively, the team may choose to evade the monster, in which case there is no reward and all of them will split the stress level, si, evenly. Your campaign is over when either evading or ghting the next monster will raise either adventurer’s stress level over S. For example: in the case where the next monster causes a stress level of 12, where the rst adventurer’s stress level is at 8, the second adventurer’s stress level is at 7, and their max stress level allowed is 10, then the campaign will be over because any action ( ghting or evading) would cause an adventurer’s stress level to go above 10. Suppose you are now given the order in which monsters will appear, their stress costs and their rewards. Use dynamic programming to devise a strategy that will maximize the total reward your team can earn before they must abandon their mission.

    1. Prove optimal substructure.

    2. Provide the recurrence relation.

    3. Design a top-down algorithm with memoization. Include the time and space complexity of your approach.

    • NP-complete

Now consider the case when Amrita’s Amazing Ice cream runs out of gallon containers. They o er to pack your ice cream into two smaller containers, and ask you which avors to put in each. Wanting to produce two equally pleasing smaller buckets, you wonder if there’s a way to divide up the avors such that the two smaller buckets B1 and B2 have exactly the same score L1

    • L2 = L2 (you may assume L is even). You do not care that the quantities of the buckets may be di erent, only that their likeability scores are the same. Unfortunately for you, you cannot come up with a good algorithm to quickly nd the best arrangement. Even worse, your best friend tells you that you may just have to settle for containers with lopsided likeability scores the next time this happens. Prove that your best friend is right by showing that this problem is NP-Complete. Remember to follow the steps from lecture to prove NP-completeness; lack of any of the steps will result in a suboptimal grade. Hint: The Subset Sum problem is that, given a set of integers S, is there a subset of S that sums to a value k? Because the subset sum problem is NP-complete, you can use it for your reduction.


3