+1 (315) 557-6473 

Design and Analysis of Algorithms Homework Help

We are associated with industry professionals and experienced computer scientists who provide immaculate design and analysis of algorithms homework help. Our tutors are tested and proven. Students who avail of our ideal design and analysis of algorithms homework help can expect correct and thoroughly researched solutions. Besides our experts work diligently to make sure that your solutions not only meets the highest standards but also delivered on time.

Currency Algorithm 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! See https://en.wikipedia.org/wiki/United_States_dollar). 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 following Greedy-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 an unlimited number of bills of f1; 2; 5; 10g 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.)
(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. (For example, you might not have any $2 bills or might only have two $20 bills.) Assume you have an 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 f1,2,5,10g 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.)
Problem 1 Solution
Let’s assume A = {c1, c2, c3, c4….ck} with C types of coins is a feasible solution 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 a sum of values (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.
b) 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

Shopping Coupon Algorithm Problem

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(n log n) time). (You do not need to prove correctness for this problem.)
(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.

Algorithm Design

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(n log n) time). (You do not need to prove correctness for this problem.)
(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(n log n) time).
Hint: Should you use coupons of type II on more expensive items or cheaper items? Once you can answer these questions the idea would be similar to (a).
2
(d) (10 points) Prove the correctness of the algorithm you designed in (c).
(extra) Of course, using all coupons of type II may not be the best option. Suppose you are free to use as many coupons of type II as you want, can you design an algorithm to compute the minimum total cost for you to buy all the n items? Just for thinking please don’t submit a solution to this problem. You should be able to get an O(n2) time algorithm although O(n log n) is also possible (but di cult).
Problem 2 solution
a)
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 takes n*log (n) +m*log (m), but m<=n so we can say it takes O (n*log (n)) after multiplying 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))
b)
Given P list with n elements and K list with K elements
You just have to sort both list P list nonincreasing order and Q list non decreasing order It takes 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)
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 takes n*log(n) +m*log(m) +k*log(k) so O(n*log(n)) then you sum all the elements from K and create 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)).
d) 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 into 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 on both sides then we can say if it replaces the expensive ones with coupons II we are going to get fewer prices.

Related Blogs