CSCI 350 Fall 2001, Homework 6

1. Delete in both binomial heaps and fibonacci heaps depends on being able to decrease the key to -infinity. Give a solution that does not depend on this and argue that the time complexity does not change.

2. CLRS 19-1, p. 473-4 (Second edition). (This is 20-1, p. 418 in first edition)

3. CLRS 20.4-1, p. 496 (second edition). (This is 21-4.1, p. 438 first edition.)

4. CLRS 20-1, parts a and b, p. 496. (This is 21-1, a and b in first edition).

Challenge Problem 11: CLRS second edition problem 19-2, 474-475. problem 20-2 in CLR first edition, p. 418-419

Challenge Problem 12: CLRS second edition problem 20.4-2, p. 496. (Problem 21.4-2 p. 438 in first edition.)

Challenge Problem 13:CLRS second edition problem 20-2, p. 497. (21-2, p. 439 in first edition.)