The outline for the talk on Thursday and Friday on the topic of minimum weight spanning tree algorithms is below. The Friday talk will be at 2:00 in room 137. People can go over pages 296-303 in the text book "Randomized Algorithms" to prepare for this topic. Thursday: Talk given by Hanwen Wu 1. Background 2. Problem Definition 3. Properties of Minimum Spanning Trees 4. deterministic Algorithm: Kruskal's 5. Deterministic Algorithm: Boruvka's 6. Heavy Edges and MST verification 7. Application and Examples Friday: Talk given by Nabeel Akhtar 1. Brief background - Minimum Spanning Tree and Minimum Spanning Forest 2. Properties and their proofs 3. Brief overview of the deterministic algorithm 4. Randomized linear-time algorithm for finding minimum spanning tree 5. Analysis of the randomized algorithm 6. Brief overview of other randomized algorithms / Applications of MST. References: Paper: A Randomized Linear Time Algorithm to find Minimum Spanning Tree Book 'Randomized Algorithm, R. Motwani and P. Raghavan' Page: 296-303