# Outline of Class 51: Graphs, Concluded

Held: Tuesday, May 5, 1998

• For those of you who want extra credit on the last exam there are makeups for problems 2 and 3 available.
• If you got most of the credit on a problem, doing the makeup gives you five extra points on the exam.
• If you got almost none of the credit on a problem, doing the makeup raises your score on the problem to twenty.
• For problem 2: implement a program that reads in integers and prints out their bias-128 representation.
• For problem 3: implement the tree traversal algorithm (you can either deverlop your own tree class or use an existing one).
• I'm asking you to grade your own homework. You should send me a short paragraph indicating what you deserve for homework and why. Here's the general algorithm.
• Start with a grade of B+. This represents "turned in every assignment in working order and with thorough comments" (normally that would be "B", but since I'm having you grade yourself I'm starting at a higher baseline).
• If you frequently neglected to write preconditions and postconditions, reduce your grade by one third of a letter grade.
• If you ocassionally neglected to write preconditions and postconditions, reduce your grade by one sixth of a letter grade.
• For each of the following extra credit components you did, add one sixth of a grade.
• Homework three (Matrix): Included `Pair` class.
• Homework four (Othello): Included graphical user interface.
• Homework four (Othello): Included automatic computer player.
• Homework four (Othello): Provided multiple rules (different size boards don't count).
• Homework five (Array-based Lists): Provided at least two useful methods not mentioned in the interface.
• Anything else equivalent (must be documented).
• For each assignment in which you turned in non-working code, but devoted a substantial amount of effort, reduce your grade by one third of a letter grade.
• For each assignment you failed to do, reduce your grade by two thirds of a letter grade.
• For each assignment with minor errors reduce your grade by one sixth of a letter grade.
• We had a question for today: Can you improve the running time of Dijkstra's algorithm by using a different data structure?
• What is computer science?
• What is mathematics?
• What is engineering?
• What is science?
• There's still time for you to complete the optional multimedia labs. If you do two or more labs, you'll get one point of extra credit towards your final grade (plus \$6/hour). Schedule labs with Evan Schnell (schnelle), Andrew Nashel (nashel), Dan Wislocki (wislocki), or Kevin Notheis (notheis).

## A Few More Algorithms

### The Minimum Spanning Tree Problem

• An interesting variant of shortest path and traveling salesperson is the minimum spanning tree (MST) problem.
• The MST of an undirected graph is a set of edges that span the graph (permit one to get from each node to every other node).
• It is minimum in the sense of having the smallest sum of edge weights.
• Note that the MST is a tree since there is no benefit to including a cycle (the extra edges can only add cost).
• It is possible to solve the MST problem by a greedy algorithm.
• Actually, I've been told that there are a variety of greedy algorithms that help solve the MST problem.
• Here's one version:
• Separate the nodes into two groups: those in the MST and those not in the MST. Initially one node is in the MST (it doesn't matter which one).
• Repeatedly pick the smallest edge between a node in the MST and a node not in the MST and add it to the MST.
• If there are any nodes left in the set of nodes not in the MST, then there is no MST.
• Here's another version.
• Here, we'll only pay attention to edges.
• Repeatedly pick the smallest edge that doesn't form a cycle with edges already in the MST and add it to the MST.
• How efficient are these two algorithms?
• The first requires us to repeatedly find the smallest edge between nodes in the MST and nodes not in the MST. That should be implementable as an O(m) operation. We do that O(n) times (there are n-1 edges in the MST), so the overall running time is O(n*m).
• The second requires us to repeatedly look at the smallest remaining edge. If we put the edges in a heap, then we can do each smallest operation in O(log_2(m)) time, giving an overally running time of O(m*log_2(m)).
• Are both algorithms correct?
• Yes
• How might we prove it?
• Suppose there is a smaller minimum spanning tree, SST.
• Pick an edge in the MST computed in the second algorithm and add it to SST.
• That edge forms a cycle. If it was in the MST, then it must have been picked before another edge in the cycle.
• This means that there is another edge in that cycle with weight greater than that of the edge we picked.
• We can improve SST by replacing that edge with the one from MST.
• So SST wasn't a minimum spanning tree.
• This proof assumes that no two edges have the same weight. With some effort, we can show that it also holds if multiple edges can have the same weight (basically, we have to find a cycle in which the edge we add has smaller weight).
• We can also ensure that no two edges have the same weight by modifying the weight of each two identical edges slightly (by a weight that is smaller than 1/(# of edges) or some such).
• Can we do the proof for the other version? Yes, but it's more difficult. Basically, we consider the point at which we add a edge to the MST that's not in the SST. There must be some other path in SST from "MST so far" to the node that edge connects. If we add the edge to the SST, we form a cycle. As before, we can then make the SST smaller by using that edge.

On to Reachability, Revisited
Back to Dijkstra's Shortest Path Algorithm
Outlines: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
Current position in syllabus

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.