Prim's and Kruskal's Algorithms, two different methods for finding the minimal cost spanning tree in a weighted graph, have become a standard part of the discrete math curriculum; they are both "greedy" algorithms, methods in which the best choice at each step of the process results in the best solution at the end of the process. But why teach both? Can they ever produce different results? In this talk, the history and applications of the algorithms will be discussed, the methods explained, important properties of minimal spanning trees revealed and a new algorithm for finding the number of different minimal spanning trees will be shown. The talk should be accessible to all students who have taken or are currently taking Math 2150.

Please join us beforehand for pizza.