5. (10 points) Greedy Algorithms You were planning to study real hard this quart

Question

5. (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) ( point) Consider the case where you have taken out 7 books. The list T has your estimated reading time for each book T-11,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

a)

for each book how much days it will take to read the book, we have to give that much dollar as cost of it.

So for the sequence {1, 5, 2, 6, 1, 4, 2} the cos will be

1 5 2 6 1 4 2

1 6 8 14 15 19 21

beacause before the 2nd book we allready have taken 1 day for the first book, so for 2nd book we have to give fine for 6 days and so on.

hence total cost= 1+6+8+14+15+19+21

= 84

b)

If we read the books in increasing order of their time taken to read then we will have the overdue cost minimized.

1,1,2,2,4,5,6 and the cost for this sequence will be = 59.

c)

Algorithm(T, n)

1. sort the sequence T in an increasing order of the time taken to read the books.

2. each time take the minimum time book and calculate the cumulative sum as overdue for the same..

3. Finally add all the overdues calculated for each book in increasing order, as overall cost

d)

The time complexity of our algorithm will be O(nlogn) for sorting n times plus traverse the sequence O(n) = O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.