Exercise 7.11 Suppose you are the "algorithmatician" of your company and the manager comes to you with the following problem. The company has to buy n different software products. Due to various constraints, the company can only buy at most one software product per month. Each software is currently selling for a price of $100. However, they become expensive cach month according to the following formula: the cost of software j increases by a factor ry >1 cach month, where ry is a known parameter. This means that if software j is purchased t months from now, it will cost $100(r,)". It is given that all price growth rates are distinct: that is, rr, for software i fj (even though at the start they all have the same price of $100). The question the manager poses for you is this: Given that the company can only buy at most one software product a month, in which order should it buy the products so that the total amount of money apent is as amall as possiblel? In particular he has the following questions: (1) Consider the following example to get started. Suppose ri = 2, a=3, and ra= 4. What is the best order to buy the three products and why? (H) Give a greedy algorithm to find the optimal order assuming that we have n products to buy and the growth rate of product i is r, 1sisn. What is the time complexity of your algorithm? (Hi) Prove that your greedy algorithm always gives the optimal ordering. (Hint: Use exchange argument.)
Exercise 7.11 Suppose you are the "algorithmatician" of your company and the manager comes to you with the following problem. The company has to buy n different software products. Due to various constraints, the company can only buy at most one software product per month. Each software is currently selling for a price of $100. However, they become expensive cach month according to the following formula: the cost of software j increases by a factor ry >1 cach month, where ry is a known parameter. This means that if software j is purchased t months from now, it will cost $100(r,)". It is given that all price growth rates are distinct: that is, rr, for software i fj (even though at the start they all have the same price of $100). The question the manager poses for you is this: Given that the company can only buy at most one software product a month, in which order should it buy the products so that the total amount of money apent is as amall as possiblel? In particular he has the following questions: (1) Consider the following example to get started. Suppose ri = 2, a=3, and ra= 4. What is the best order to buy the three products and why? (H) Give a greedy algorithm to find the optimal order assuming that we have n products to buy and the growth rate of product i is r, 1sisn. What is the time complexity of your algorithm? (Hi) Prove that your greedy algorithm always gives the optimal ordering. (Hint: Use exchange argument.)
C++ Programming: From Problem Analysis to Program Design
8th Edition
ISBN:9781337102087
Author:D. S. Malik
Publisher:D. S. Malik
Chapter10: Classes And Data Abstraction
Section: Chapter Questions
Problem 19PE
Related questions
Question
Transcribed Image Text:Exercise 7.11
Suppose you are the "algorithmatician" of your company and the manager comes to you with
the following problem. The company has to buy n different software products. Due to various
constraints, the company can only buy at most one software product per month. Each software is
currently selling for a price of $100. However, they become expensive each month according to
the following formula: the cost of software j incresses by a factor ry > 1 each month, where r, is
a known parameter. This means that if software j is purchased t months from now, it will cost
$100(r,). It is given that all price growth rates are distinct: that is, r, #r, for software i + j
(even though at the start they all have the same price of $100).
The question the manager poses for you is this: Given that the company can only buy at most
one software product a month, in which order shoukd it buy the products so that the total amount
of money spent is as small as poasible? In particular he has the following questions:
(1) Consider the following example to get started. Suppose ri = 2, ra = 3, and ra = 4. What is
the best order to buy the three products and why?
(ii) Give a greedy algorithm to find the optimal order assuming that we have n products to
buy and the growth rate of product i is r, 1<i< n. What is the timne complexity of your
algorithm?
(iii) Prove that your greedy algorithm always gives the optimal ordering. (Hint: Use exchange
argument.)
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Similar questions
Recommended textbooks for you
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning