CS270 Homework 3 Solution

GRADED
1. Suppose you want to drive from USC to Santa Monica. Your gas tank, when full, holds enoughgas to go p miles. Suppose there are n gas stations along the route at distances d1 ≤ d2 ≤ ... ≤ dn from USC. Assume that the distance between any neighboring gas stations, and the distance between USC and the first gas station, as well as the distance between the last gas station and Santa Monica, are all at most p miles. Assume you start from USC with the tank full. Your goal is to make as few gas stops as possible along the way. Give the most efficient algorithm to determine which gas stations you should stop at and prove that your algorithm yields an optimal solution (i.e., the minimum number of gas stops). Give the time complexity of your algorithm as a function of n. (15 points)
2. The array A holds a max-heap. What will be the order of elements in array A after a newentry with value 18 is inserted into this heap? Show all your work. A = 19, 17, 14, 8, 7, 9, 3, 2, 1, 4 (8 points)
3. (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 cent). Prove that your algorithm yields an optimal solution. (Hints: consider how many pennies, nickels, dimes, and dimes 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. (15+5 points)
4. You are given positions of N Mice and positions of N holes on a 1-dimensional number line.Each hole can accommodate at most 1 mouse. A mouse can stay in place, move one step right from x to x + 1, or move one step left from x to x − 1. Devise an algorithm to assign mice to holes so that the number of moves taken by the mice is minimized. Your algorithm should return the minimum number of moves taken to assign mice to holes and be in O(N log N) time. (10 points).
5. Farmer John has N cows (1, 2,..., N) who are planning to escape to join the circus. His cowsgenerally lack creativity. The only performance they came up with is the “cow tower”. A “cow tower” is a type of stunt in which every cow (except for the bottom one) stands on another cow’s back and supports all cows above in a column. The cows are trying to find their position in the tower. Cow I (i = 1, 2,... , N) has weight Wi and strength Si. The “risk value” of cow i failing (Ri) is equal to the total weight of all cows on its back minus Si. We want to design an algorithm to help cows find their positions in the tower such that we minimize the maximum “risk value” of all cows. For each of the following greedy algorithms either prove that the algorithm correctly solves this problem or provide a counter-example. Hint: One of the two solutions is correct and the other is not.
(a) Sort cows in ascending order of Si from top to bottom
(b) Sort cows in ascending order of Si+Wi from top to bottom. (15 points total)
UNGRADED
1. The array A holds a max-heap. What will be the order of elements in array A after the entry with value 14 is removed from this heap? Show all your work. A = 19, 18, 14, 8, 17, 9, 3, 2, 1, 4, 7