York University - CSE 3101 - Summer 2006
Phuong Nguyen

Summary of Lecture 6:

1. Solution to the test.

2. Prove the correctness of the Activity Scheduling Problem.
The proof is by showing that every partial solution S_i is "promising".
Here S_i is promising if it can be extended to an optimal solution
using activities only from {A_{i+1}, ..., A_n}.

3. Graph theory terminologies. Introduced the Minimum Spanning Tree Problem.

References: See discussion of the Activity Selection Problem in Section 16.1.
See also Section 16.2.
For MST see Chapter 23.