The New Turing Omnibus Chapter 22: Minimum spanning trees

Jump to bottom Edit New page

Dmitry Kandalov edited this page Oct 20, 2016 · 4 revisions

Meeting panorama

Snacks!

Snack time!

MINSPAN (the algorithm in the book)

Chris Patuzzo shows us a minimum spanning tree Stepping through the algorithm by hand Murray Steele is confused by the algorithm and draws a tree to try and understand

Discussing the proof in the book

We have a debate about the proof described in the book Some diagrams we drew to help us understand the proof Tom Stuart draws a tree to help us underestand the proof in the book

Steiner trees

Tom Stuart draws a steiner tree Tom Stuart describes a possible solution to the steiner tree problem

Tom also mentioned how seemingly similar minimum spanning tree and travelling salesman problems end up having very different complexities.

Show'n'tell

Dmitry Kandalov shows off Chris Patuzzo's Javascript implementation of the algorithm Chris' JS implementation

Dmitry Kandalov shows off his own Kotlin implementation of the algorithm Dmitry's Kotlin implementation

Afterwards!

Pub panorama

References

Acknowledgements

Thank you to Leo and Geckoboard for hosting, and to Chris P. for shepherding.