Description

Neel Gupta
Problem 1. Suppose you want to drive from USC to Santa Monica. Your gas tank, when full, can hold enough gas to go p miles. Suppose there are n gas stations along the route at distances d1 ≤ d2 ≤ … ≤ dn from USC. Assume that all di − dj ≤ p when i = 2, 3, …, n and j = i − 1. Assume you start with a full gas tank. 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.
Answer: Starting from USC, choose the farthest gas station within p miles and eliminate any closer gas stations. Now starting from that gas station, go p more miles until reaching the new furthest gas station. Choose that gas station, eliminate closer stations, and repeat.

Algorithm 1 Determine which gas stations to stop at

Let D be the set of gas station’s distances that are assumed to be sorted procedure MINGASSTOPS(D)
Let S be the resulting set; S ← ∅
Let g be the number of gas stops taken; g ← 0 Let distanceTraveled ← 0
for every station si at distance Di when i = 1, 2, …, n do if Di−distanceTraveled > p then g ← g + 1
distanceTraveled ← Di−1 S = S ∪ {si−1} end if
end for
return g end procedure

This algorithm runs in O(n) and uses a greedy approach under the criteria of choosing the gas station that is at most p miles from the current distance traveled.
Consider our algorithm and an optimal algorithm that respectively return sets S := {s1, s2, …, sg} and O := {t1, t2, …, th}. Since our first stop is s1, we show that there is an optimal solution beginning at s1. If t1 = s1, then O is a valid optimal solution under this criteria. If t1 ̸= s1, then t1 is before s1 since our greedy algorithm takes the furthest station within our gas tank range. Now consider the solution set O′ := {s1, t2, …, th}, then |O| = |O′|. Second, we need to consider whether O′ is valid. By acting greedily, we can reach s1. Since O is optimal, there is at least enough gas to go from t1 to t2 and because t1 is at most as far as s1, then there is enough gas to go from s1 to t2. Therefore O′ is just as optimal as O, then by exchange arguments, if you swap any si ∈ S with any element in O, the solution will be just as optimal as any arbitrary optimal solution. Thus, S itself is optimal.
Problem 2. The array A holds a max-heap. What will be the order of elements in A after a new entry with value 18 is inserted into this heap? Show all your work. A = 19, 17, 14, 8, 7, 9, 3, 2, 1, 4.
Answer: A expressed as a binary max-heap: 19

2 1 4
After adding 18 to the heap, A = 19, 17, 14, 8, 7, 9, 3, 2, 1, 4, 18.
19
3
2 1 4 18
19 19

→ 2 1 4 7 → 2 1 4 7
After trickling up, A = 19, 18, 14, 8, 17, 9, 3, 2, 1, 4, 7
Problem 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. (Hint: 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 shold include a penny so that there is a solution for every value of n.
Answer: (a) A greedy algorithm to achieve this task would be to take the biggest possible coin denomination at each iteration and subtract this value from n until the smallest coin denomination does fit within the remaining balance. If this algorithm terminates with a balance equal to 0, then there exists a possible solution set S with denominations to make change of n cents.
procedure COINCHANGE(n)
Let d be a list of coin denominations 25, 10, 5, 1
sort(d) in ascending order res ← 0
maxIndex ← len(d)-1 while n > 0 do
if n ≥ d[maxIndex] then
n ← n − d[maxIndex]
res ← res + 1
else
maxIndex ← maxIndex-1 if maxIndex = −1 then return -1
end if
end if
end while if n = 0 then return res else return -1
end if end procedure
If n < 5, use n pennies. If 5 ≤ n < 10, use 1 nickel and n − 5 pennies. If 10 ≤ n < 25, use ⌊n/10⌋ dimes. If 25 ≤ n, use ⌊n/25⌋ quarters and use the former 3 cases on n − 25⌊n/25⌋.
Consider using pennies and nickels. At most, there can be 4 pennies because any 5 pennies can be replaced by a nickel, and this switch reduces the number of coins by 4. If n ≡ 0 mod 5, then we would only use nickels and no pennies. We would use as many nickels as possible before going to pennies.If the remainder is more than 5, we could use both nickels and pennies.
Consider using pennies, nickels, and dimes. At most, there can be 1 nickel because any 2 nickels would be replaced by a dime which would reduce the coin count by 1.If n ≡ 0 mod 10, we would only use dimes and no nickels or pennies. We would use as many dimes as possible before going to smaller coins. If the remainder is more than 10, we could use both pennies, nickels and dimes.
Consider using all coins. At most, there can be 2 dimes since 3 dimes would become a quarter and a nickel which reduces the coin count by 1. If the remainder is more than 30, we would use the combination of as many quarters and nickels as possible. Then the number of nickels would combined into dimes according to the second consideration, so if the remainder is greater than 30, take as many quarters as possible.
Consider a remainder of above 25 cents but below 30 cents without quarters. According to the first 3 rules, we would take 2 dimes, 1 nickel, and n − 25 pennies. We could reduce the coin count by replacing the 2 dimes and nickel with a quarter, reducing the total coin count by 2.
Since every case of using k different types of coins to then using k + 1 different types of coins reduces the total coin count, a greedy approach provides the optimal solution for this problem.
(b) The greedy algorithm would not yield the optimal solution for the following set of coin denominations, {1, 90, 100}. Considering when n = 380, the greedy solution proposed would return 83 since after we take 3 of the 100 cent coins, we need 80 of the 1 cent coins. A far more optimal solution for this case would be to take 2 100 cent coins and then 2 80 cent coins to make the total.
Problem 4. You are given the position of N mice and N holes on a 1dimensional number line. Each hole can accomodate at most 1 mouse. A mouse can stay in place, move one step right from location x to x + 1, or move one step left from location 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.
Answer: This problem can be solved with a greedy approach. Moving every mouse to its nearest hole can minimize the time. After sorting both mouse positions and hole positions, pairing the ith mouse with the ith hole when i = 1, 2, …, N will give us the minimum number of steps by subtracting ith mouse’s spot from how for they have to go to go get to the ith holes. Summing the absolute value of this difference will give us the minimum number of steps that all mice have to take.
Let M be mice positions Let H be hole positions
procedure MOUSE2HOLES(M,H)
res ← 0 sort(M) sort(H) for i = 1, 2, …, N do
res ← res+|Mi − Hi|
end for
return res end procedure
This algorithm runs in O(N log N) which is the time taken to sort the mouse and house positions lists. Consider the following mice at positions M1 and M2 s.t. M1 < M2 and the following house positions H1 and H2 s.t. H1 < H2. By exchange arguments, it suffices to show that |M1 − H1| + |M2 − H2| ≤ |M1 − H2| + |M2 − H1|, so any swap between mice and houses causes a worse travel time.
Problem 5. Farmer John has N cows numbered 1, 2, …, N who are planning to escape and join the circus. His cows will be in a cow tower to try and escape where cowi has weight Wi and strength Si when i = 1, 2, …, N. The risk value 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 s.t. 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 counterexample.
(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.
Answer: (a) Consider the following counterexample.
S := {3, 2, 1} and W := {3, 5, 2}, then the cow with the highest strength will be on the bottom which has strength equal to 3 but risk equal to 4. If cow2 were on the bottom, the risk would then be equal to 3 which is less than 4, so sorting in ascending strength as our greedy criteria does not always yield the most optimal solution.
(b) Define an inversion in a solution that is Si +Wi for cowi is more than Sj + Wj for cowj but cowj is below cowi in the cow tower. We can show that inversions can be removed without increasing the overall maximum risk. Given an optimal solution, we show that we can remove inversions without affecting the overall optimality of the solution. If an inversion exists between cowi and cowj, then either cowi and cowj are adjacent or there is a pair of cows between cowi and cowj that are adjacent and have an inversion. Assume cowi and cowj are adjacent and have an inversion. Now we can show that moving cowi below cowj will not increase the risk of either cow.
We can move cowi below cowj, but we will not increase Ri because our greedy assumption cowi is stronger or heavier than cowj.
We can then move cowj above cowi, and Rj is not decreased as a result of this because either cowi can hold more or cowi’s heavier weight does not need to be held up by cowj, and both of these situations reduce the overall risk.
Since we know that removing an inversion will not affect the overall risk negatively, if we are given an optimal solution with any inversions in it, we can remove these wihtout affecting the solution’s optimality. When there are no more inversions, the solution will be the same as ours, that the cows are sorted in order of strength plus weight. Thus, our solution is optimal.