Welcome back!   I hope you enjoyed your break.
Winter is officially over tomorrow (vernal equinox).

Today I'll return your graded midterm exam, and go over solutions.
The midterm is online among the handouts, and see ../0307/H.jpg for
the blackboard image of graph H.

Basic stats: 32 students took it, max possible raw score was 56, the
quartile raw scores were 42, 38, 33.5.  Aftertthe curve, many
high-achiever students may find they only got an A- or B+, but nobody
failed either.  (Good students typically do better on my homework than
on my exams.)

Our next topic is minimum spanning tree (MST) algorithms, Section 4.3.
And more generally, greed.  I actually said a bit about this Friday
before break, but I'll redo it today.

The MST problem:
    Given connected graph G with edge weights, find tree T that spans
    all the vertices, and so its total edge weight is minimum.
    (Or if G not connected, T is a forest spanning each component.)

It turns out that there are efficient solutions to this problem,
because a simple greedy approach actually finds the best solution.
"Greed" does not always work optimally, but it does here.

Your next homework is not ready, but I expect we'll look at greedy
approaches to the TSP (traveling salesman problem).  The TSP is a
problem that resembles the MST, but where greed is not optimal.

Resources:
43MinimumSpanningTrees.pdf
    section notes:
    API for a graph with edge weights
    API for the MST (a list of edges)
    The cut property: min-weight crossing edge is in the MST.
    (Or with ties: a min-weight crossing edge is in some MST.)
    basic greedy algorithm (43DemoGreedy.pdf)
    Kruskal's algorithm (sort edges, PQ+UF, 43DemoKruskal.pdf)
    Prim's algorithm (grow one tree, PQ, 43DemoPrim.pdf)