Unformatted text preview:

CSCI 570 - Fall 2021 - HW 3Due September 16, 20211 You have N ropes each with length L1, L2, . . . , LN, and we want to connectthe ropes into one rope. Each time, we can connect 2 ropes, and the costis the sum of the lengths of the 2 ropes. Develop an algorithm such thatwe 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 differenttypes of liquid with amount L1, L2, . . . , LNand with value V1, V2, . . . ,VN. Assume that mixing liquids doesn’t change their values. Find analgorithm 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. Yourgas tank, when full, holds enough gas to go p miles, and you have a mapthat contains the information on the distances between gas stations alongthe route. Let d1< d2... < dnbe the locations of all the gas stationsalong the route where diis the distance from USC to the gas station. Weassume that the distance between neighboring gas stations is at most pmiles. Your goal is to make as few gas stops as possible along the way.Give the most efficient algorithm to determine at which gas stations youshould stop and prove that your strategy yields an optimal solution. Givethe 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 fewestnumber of coins. Describe a greedy algorithm to make change consisting ofquarters(25 cents), dimes(10 cents), nickels(5 cents) and pennies(1 cents).Prove that your algorithm yields an optimal solution. (Hints: considerhow many pennies, nickels, dimes and dime plus nickels are taken by anoptimal solution at most.) (20 points)(b) For the previous problem, give a set of coin denominations for whichthe greedy algorithm does not yield an optimal solution. Assume thateach coin’s value is an integer. Your set should include a penny so thatthere 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)17 (Not Graded) There are N tasks that need to be completed by 2 computersA and B. Each task i has 2 parts that takes time ai(first part) and bi(second part) to be completed. The first part must be completed beforestarting the second part. Computer A does the first part of all the taskswhile computer B does the second part of all the tasks. Computer A canonly do one task at a time, while computer B can do any amount of tasksat the same time. Find an O(nlogn) algorithm that minimizes the time tocomplete all the tasks, and give a proof of why the solution is


View Full Document

USC CSCI 570 - HW 3

Download HW 3
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view HW 3 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view HW 3 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?