Order Now  +1 678 648 4277 

Top-Notch Design and Analysis of Algorithms Assignment Help

This is a Design and Analysis Algorithms Assignment Help sample. It was developed by A Programming Assignment Help expert from our platform. The sample shows how to use the greedy-pay algorithm to minimize payment and show the conditions under which it fails to do so. The Programming Homework Help solutions also show how to come up with an algorithm that can minimize cost and cost and another one which can compute the total minimum cost.

Design And Analysis of Algorithms Assignment Help
Table Of Contents
  • Using the Greedy-Pay algorithm to minimize payment

Using the Greedy-Pay algorithm to minimize payment

Problem 1 (Currency System).

 As we all know, the US dollar is the official currency in the United States. There are different bills of value 100,50,20,10,5,2,1 (although we rarely see $2 bills, they do exist! In this problem, we consider the problem of buying something with the smallest number of bills. A simple way to pay x dollars is to use the followingGreedy-Pay algorithm:
Greedy-Pay(x)
While x > 0
 Let u be the bill of largest value such that u <= x
Pay the bill with value u
Let x = x - u
(a) (12 points) Prove that if you have unlimited number of bills of{1,2,5,10}dollars (and you don’t have any other bills), no matter what x is (x is an integer), the Greedy-Pay algorithm minimizes the number of bills used for the payment. (Change is not allowed here. For example, you cannot pay $9 by a $10 bill and get $1 back.)
Solution
Let’s assume A={c1, c2, c3, c4….ck} with C types of coins is afeasiblesolution for M if exists c in C sumOfValues (A) +value(c) is less or equal than M A’= {c1, c2, c3, c4… ck, c} is a feasible solution too.
So this strategy always you can ensure if exist c until sumOfValues (A) exist the solution and the algorithm can get the solution.
In this case we have C= {1, 2, 5, 10} we can ensure that exists the solution because 1 is in C, also new know x=L*10+j where j 0<=j<=9, the algorithm will get the optimal solution getting L coins of 10 value, for any value between 1 and 9 get the optimal solution we can show all cases in this table.
Number of coins
  1 2 3 4 5 6 7 8 9
1 1                
2 2 1,1              
3   2,1 1,1,1            
4   2,2 2,1,1 1,1,1,1          
5 5   2,2,1 2,1,1,1 1,1,1,1,1        
6   5,1 2,2,2 2,2,1,1 2,1,1,1,1 1,1,1,1,1,1      
7   5,2 5,1,1 2,2,2,1 2,2,1,1,1 2,1,1,1,1,1 1,1,1,1,1,1,1    
8     5,2,1 5,1,1,1- 2,2,2,2 2,2,2,1,1 2,2,1,1,1,1 2,1,1,1,1,1,1 1,1,1,1,1,1,1,1  
9     5,2,2 5,2,1,1 5,1,1,1,1- 2,2,2,2,1 2,2,2,1,1,1 2,2,1,1,1,1,1 2,1,1,1,1,1,1,1 111111111

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.