DS C9 Review

Corrections of PTA

HW 9

Let S be the set of activities in Activity Selection Problem. Then the earliest finish activity $a_m$ must be included in all the maximum-size subset of mutually compatible activities of S.

Correction: False

The Activity Selection Problem could be solved by Greedy Algorithm: One solution given, with the earliest finish activity. However, not all solutions choose the he earliest finish activity. Take the following example:

Both $S_1 = \{a_m,a_2,a_4,a_5\}$ and $S_2 = \{a_1,a_2,a_4,a_5\}$ could be accepted as the best solution. However, only $S_1$ will be given by Greedy algorithm.

HW 11

Greedy method is a special case of local search.

Correction: False

Local search is a process of iterating the solutions, which means the solutions are possible( but may not be optimal) at any moment.

However the Greedy method only gives one best solution at the end of process.