• 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.
• 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.
• 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.
• (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.)
(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.
• Solve Kleinberg and Tardos, Chapter 3, Exercise 3.
6 Solve Kleinberg and Tardos, Chapter 4, Exercise 4.
1
• (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
