4. (10 points) Greedy Algorithms You were planning to study real hard this quart
ID: 3724420 • Letter: 4
Question
4. (10 points) Greedy Algorithms You were planning to study real hard this quarter so you took out n books on algorithms. However you had better planning than execution and you have not read a single book and they are now all overdue. The library charges one dollar a day for each overdue book. You have calculated for each book the number of days it will take you to read the book. You want to know what order to read (and return) the n books so that your overdue costs are minimized. a) (1 point) Consider the case where you have taken out 7 books. The list T has your estimated reading time for each book. T-1,5,2,6,1,4,2] If you read the books in this order (and return a book when you are done) what will be the final cost? b) (2 points) What order should you read the books to minimize your costs? What is the cost when you read them in your suggested order? c) (2 points) Describe a greedy algorithm that will solve this problem for a general instance.Explanation / Answer
Solution:
a)
If we are reading the books in the same order as given
the order is [1, 5, 2, 6, 1, 4, 2]
on Day 1 the overdue cost will be 1+5+2+6+1+4+2 = $7
Day 2=> 5+2+6+1+4+2 = $6 (1 day is done so the first book is returned now)
Day 3=> 5+2+6+1+4+2 = $6
Day 4=> 5+2+6+1+4+2 = $6
Day 5=> 5+2+6+1+4+2 = $6
Day 6=> 5+2+6+1+4+2 = $6
Day 7=> 2+6+1+4+2= $5
and so on
total cost = 7 + (5*6) + (2*5) + (6*4) + (1*3) + (4*2) + (2*1) = $84
b)
If the books are read in sorted order from minimum number of days to max then the cost will be minimized according to the greedy approach.
In this case the
total cost = 7 + (1*6) + (2*5) + (2*4) + (4*3) + (5*2) + (6*1) = $59
c)
The algorithm will be
Algorithm:
The above algorithm will take T(n)= O(n log n) time.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.