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.