### Notes on a Derivation of Activity-Selection

I wrote some brief notes explaining the Partial Greedy Theorem and a derivation of an algorithm for the Activity-Selection problem taken from Chapter 16 of *Introduction to Algorithms, second edition* (Cormen et al, 2001). Some tedious details are omitted in the notes but (painfully) verified in AoPA.

The main derivation is:

One can see that the rightmost `fin-ordered`

in the specification propagates itself into the generating fold and absorbs redundant coreflexives, which somehow justifies that sortedness of the input list is indeed essential to the derived algorithm.

--

Please click the title for the notes.

Labels: Program Derivation

<< 回到主頁