Question 6: Greedy Algorithm (15 points) Consider the problen of storing n books

Question

Question 6: Greedy Algorithm (15 points) Consider the problen of storing n books on shelves in aiby. The order of the books is fixed by the cataloging system and so cannot be rearranged. Therefore, we can spealk of a book b where 1 s i Sn, that has a thickness ti and height hi The length of each bookshelf at this library is Suppose all the books have the same height h (ie h-hi hj for all i,j) and the shelves are all separated by a distance of greater than h, so any book fits on any shelf. The greedy algorithm would fill the first shelf with as many books as we can until we get the smallest i such that b does not fit, and then repeat with subsequent shelves. Show that the greedy algorithm always finds the optimal shelf placement, and analyze its time complexity.

Explanation / Answer

Solution:

a) Consider a set of three books, each of thickness 1, and with the first book having height 1, and the second and
third books having height 2. Suppose that L = 2. Clearly, the b1 must be placed on the first shelf. The greedy
algorithm then places b2 on the first shelf. This now fills the first shelf, and so we then must place b3 on the
second shelf.
Since the largest book on each shelf is of height 2, the cost of this layout is 4. However, we can do better. Instead
of this layout, we can place the first book on the first shelf, and the last two books on the second shelf. In this
case, the first shelf has only one book of height 1, and the second shelf has books only of height 2, and so the
cost of this layout is 3, which is better than what the greedy algorithm produced. Notice that this example is
simple, which is why it is the best example. The simplest example is the best example!
You should write a proof of the optimality of the greedy algorithm for the case where all the book heights are
constant (problem 3-1), and determine what in that proof goes wrong in the case of non-equal heights.

e)prodecure PLACEBOOKS (H; T )
var
2
COST : array(1::n) of real;
currentshelf : real;
i; j; start : integer;
begin
COST[n] := H[n];
for i := n
1 downto 1 loop
currentshelf := T [i];
Append start to left end list.
for j := i + 1 to n loop
currentshelf := currentshelf + T [j];
if currentshelf L and
maxfH[i];:::;H[j]g + COST [j + 1] COST [i] then
COST [i] = maxfH[i];:::;H[j]g + COST [j + 1]
N extShelf [i] = j + 1
end if;
end for loop;
end for loop;
end PLACEBOOKS

Please, please upvote and raise your doubts within the comments.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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