Description

points)
2. There are N tasks that need to be completed by 2 computers A and B. Each task “i” has 2 parts that take time: ai (first part) and bi (second part) to be completed. The first part must be completed before starting the second part. Computer A does the first 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. (15 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 𝑑1 < 𝑑2 < . < 𝑑𝑛 be the locations of all the gas stations along the route where 𝑑𝑖 is the distance from USC to the gas station. We Your goal is to make as few gas stops as possible along the way. Give𝑝 the assume that the distance between neighboring gas stations is at most miles.
most efficient 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 𝑛. (15 points)
number of coins. Describe a greedy algorithm to make change consisting of𝑛 4. (a) Consider the problem of making change for cents using the fewest
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.
5. Suppose you are given two sets A and B, each containing n positive integers. You can choose to reorder each set however you like. After reordering, let ai be the i-th element of set A, and let bi be the i-th element of set B. You then
receive a payoff on 𝑛 𝑏 .Give an algorithm that will maximize your ∏=0 𝑎𝑖 𝑖
payoff (6 points). Prove𝑖 that your algorithm maximizes the payoff(10 points) and state its running time (4 points).
7. The array A below holds a max-heap. What will be the order of elements in array A after a new entry with value 19 is inserted into this heap? Show all your work. A = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1}