Trees (Minimum Spanning and Binary Search)

  • Kruskal's handout and example problem and data.
  • Kruskal's original, more readable version of the above handout. This will be handed out on Tuesday, November 28th and Wednesday, November 29th, 2000 in class.

    1. I will show the solution to the Kruskal MST example problem data and my answers to questions 1, 2, 3 and 4 during class.
    2. I will show some hints for question #5 as well. Your lecture notes for Monday, April 24th are probably enough, but a solution shown here will be useful supplement to those notes and the messy blackboard examples.

  • The Kruskal's algorithm, homework is due during the last week of class. It might be a two coin flip homework.

  • Kruskals algorithm for creating a minimum spanning tree from a connected, weighted graph is covered on page 440 of our textbook.

  • Prim's algorithm is discussed on page 435 of our textbook. It is an alternative approach to creating a MST from a weighted, connected graph. Focus on Kruskal's algorithm instead.