Top-Notch Design and Analysis of Algorithms Homework Help

Using the Greedy-Pay algorithm to minimize payment

Problem 1 (Currency System).

Solution

So we can get the optimal solution using this way.

Circumstances in which Greedy-Pay algorithm doesn’t minimize payment

b. (8 points) Show an example for which the Greedy-Pay algorithm does not minimize the number of bills used, when you have a limited number of bills. Assume you have unlimited number of $1 bills so you have enough money to pay.

(Note: Your example should consist of an x - the amount you need to pay, and a set of bills you have. Your example can use all the types of bills mentioned in the problem (i.e., not limited to {1,2,5,10} as in (a)). You should be able to pay the amount x using fewer bills than what Greedy-Pay uses, describe what bills you will use and what bills Greedy-Pay will use.)

Solution

This is a variation knapsack problem because if you use a coin you can’t reuse, we can see in this example

{1, 3, 3, 4}

We have infinite 1 coins and we want to change 6, using the algorithm greedy it exchange 4, 1 and finally 1 when the answer is 3, 3

Designing An Algorithm To Minimize Cost

Problem 2 (Coupons)

Suppose you are shopping at a supermarket. There are n items that you want to buy, and their prices are p1,p2,...,pn. The supermarket provides m (for some m ≤ n) coupons, where each coupon has a number 0 < qi < 1 (for all 1 ≤ i ≤ m) on it. If you apply coupon i to item j, then you only need to pay qipj for item j. Each coupon can only be used for one item, and you cannot apply two coupons simultaneously on the same item.

(a). (5 points)

Design an algorithm to compute the minimum total cost for you to buy all the n items. Analyze its running time (your algorithm should run in O(nlogn) time).

Solution

Given P list with n elements and Q list with m elements

You just have to sort both list P list non increasing order and Q list non decreasing order It take n*log (n) +m*log (m), but m<=n so we can say it takes O (n*log (n)) after multiplies each value from both lists until list Q ends then you add the remaining values in P, you get the minimum total cost.

It takes O (n) so all the algorithm takes O (n*log (n))

Designing An Algorithm To Compute Total Minimum Cost

(b) (5 points)

 Now the supermarket provides a second type of coupon. There are k (where k ≤ n) such coupons, where each coupon of type II has a number fi on it. If you apply coupon i of type II to item j, then you only need to pay fi for item j, regardless of its original price. Again, each coupon can only be used for one item, and you cannot apply two coupons (no matter whether they are of the same type or not) simultaneously on the same item.

Suppose you only have the k coupons of type II (and no coupons of type I), design an algorithm to compute the minimum total cost for you to buy all the n items. Analyze its running time (your algorithm should run in O(nlogn) time). (You do not need to prove correctness for this problem.)

Solution

Given P list with n elements and K list with K elements

You just have to sort both list P list non increasing order and Q list non decreasing order It take n*log(n) +m*log(m) , but m<=n so we can say it takes O( n*log(n)), you have 2 indices i, j one for each list, you compare each list if P[i]>K[j] so both indices increase and you add coupon value Q[j] to the price if P[i]<=K[j] you increase I and add P[i] to the price, if i==n the algorithm ends and return the price value else if j==m you sum the values P[i]+P[i+1]+….P[n] to the price. This algorithm takes O (n*log (n))

(c). (10 points)

Now suppose you have both coupons of type I and II (the total number of coupons m + k ≤ n), and you need to use all coupons of type II. Design an algorithm to compute the minimum total cost for you to buy all the n items. Analyze its running time (your algorithm should run in O(nlogn) time).

Solution

Given P list with n elements and Q list with m elements and K with k elements

You just have to sort the lists P list non increasing order and Q list non decreasing order It take n*log(n) +m*log(m) +k*log(k) so O(n*log(n)) then you sum all the elements from K and creates a new list L’=P[k..n) and calls algorithm in the example (a) with L’ and P (m<=n-k) it takes (n-k)*log (n-k) so it takes O (n*log (n)).

Proving The Correctness Of The Algorithm Above

(d). (10 points): Prove the correctness for the algorithm you designed in (c).

Solution

Once you sorted the prices you have to options use the type II coupons on the k cheaper one o the more expensive, we are going to do two cases first case we split the list in two parts

P=cheaper + leftA

P=leftB+ expensive

Where length (cheaper) =length (expensive) = k

So we is easy to see that leftA is expensive than elseB so to apply the algorithm (a) in leftA and in leftB would be the price in the leftB will be less than the price in leftB.

We can see we are going to add the sum of all coupons type II both sides then we can say if it replaces the expensive ones with coupons II we are going to get fewer prices.