16.5-1
Solve the instance of the scheduling problem given in Figure 16.7, but with each penalty replaced by .
We begin by just greedily constructing the matroid, adding the most costly to leave incomplete tasks first. So, we add tasks . Then, in order to schedule tasks or we need to leave incomplete more important tasks. So, our final schedule is to have a total penalty of only .
16.5-2
Show how to use property 2 of Lemma 16.12 to determine in time whether or not a given set of tasks is independent.
Create an array of length containing zeros in each entry. For each element , add to . If , return that the set is not independent. Otherwise, continue. If successfully examine every element of , return that the set is independent.