Minimum-Weight Spanning Tree (MWST) algorithm and its correctness and complexity.
Notesupdated 24.01.12 to include the correctness proof of MWST.
Prim's algorithm, with an example.
Notes (updated 25.01.12 to correct a couple of errors in the algorithm pseudocode; updated 01.02.12 to correct the labelling on the first graph on page 2.)
Forests. Kruskal's algorithm with example and discussion of correctness and complexity.
NOTES: we hardly got on to this topic, so it is carried over to Week 4 and the notes will appear then. In the meantime you can look ahead using the links on the right...