CSCI 570 Fall 2021 HW 3 Due September 16 2021 1 You have N ropes each with length L1 L2 LN and we want to connect the ropes into one rope Each time we can connect 2 ropes and the cost is the sum of the lengths of the 2 ropes Develop an algorithm such that we minimize the cost of connecting all the ropes 10 points 2 You have a bottle that can hold L liters of liquid There are N di erent types of liquid with amount L1 L2 LN and with value V1 V2 VN Assume that mixing liquids doesn t change their values Find an algorithm to store the most value of liquid in your bottle 10 points 3 Suppose you were to drive from USC to Santa Monica along I 10 Your gas tank when full holds enough gas to go p miles and you have a map that contains the information on the distances between gas stations along the route Let d1 d2 dn be the locations of all the gas stations along the route where di is the distance from USC to the gas station We assume that the distance between neighboring gas stations is at most p miles Your goal is to make as few gas stops as possible along the way Give the most e cient algorithm to determine at which gas stations you should stop and prove that your strategy yields an optimal solution Give the time complexity of your algorithm as a function of n 20 points 4 a Consider the problem of making change for n cents using the fewest number of coins Describe a greedy algorithm to make change consisting of quarters 25 cents dimes 10 cents nickels 5 cents and pennies 1 cents Prove that your algorithm yields an optimal solution Hints consider how many pennies nickels dimes and dime plus nickels are taken by an optimal solution at most 20 points b For the previous problem give a set of coin denominations for which the greedy algorithm does not yield an optimal solution Assume that each coin s value is an integer Your set should include a penny so that there is a solution for every value of n 10 points 5 Solve Kleinberg and Tardos Chapter 3 Exercise 3 15 points 6 Solve Kleinberg and Tardos Chapter 4 Exercise 4 20 points 1 7 Not Graded There are N tasks that need to be completed by 2 computers A and B Each task i has 2 parts that takes time ai rst part and bi second part to be completed The rst part must be completed before starting the second part Computer A does the rst part of all the tasks while computer B does the second part of all the tasks Computer A can only do one task at a time while computer B can do any amount of tasks at the same time Find an O nlogn algorithm that minimizes the time to complete all the tasks and give a proof of why the solution is optimal 2
View Full Document
Unlocking...