

Covered this week:
 Lecture 1:
 MinimumWeight Spanning Tree (MWST) algorithm and its correctness and complexity.
Notes updated 24.01.12 to include the correctness proof of MWST.
 Lecture 2:
 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.)
 Lecture 3:
 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...
