# 15110 Fall 2011 [Cortina/von Ronne]

## Lab 11 - Sorting Networks and Minimum Spanning Trees

*You may work on this lab with another student if you wish.
If you do, put a comment in the program code that includes both
of your names, and both of you should submit the code.*

### Sorting Networks

To the right is a wiring diagram for a sorting network that will
sort six values. Each vertical line represents a comparison element
with its inputs coming in from the left and outputs being sent out
to the right.

- On paper, trace the operation of this sorting network on the input
2, 8, 3, 9, 0, 7. (If your CA gives you a different input, use
it instead.)
- Which comparisons in this diagram can be performed concurrently?
- How many steps does it take to sort concurrently?
(record your answer on paper)
- Do you recognize the sorting algorithm? What is it?

### Minimum Spanning Trees

The following algorithm can be used to find the minimum spanning
tree of a graph:

- Set
*n* equal to the number of nodes in *graph*.
- Set
*pq* equal to a new array of size *n*. Then initialize each element
at the index \(i\) to the value \(i\). (That is, set pq[0] = 0, pq[1] = 1, etc.)
- Set
*cost* equal to a new array of size *n*. Then initialize each
element in this array to `Infinity`.
- Set
*parent* equal to a new array of size *n*. You do not need to
initialize this array.
- While the length of the array
*pq* is greater than 1, do the following:
- Remove the first element from the array
*pq* and set *current*
equal to this value.
- For every element
*i* in array *pq* do the following:
- Set
*w* equal to the weight (stored in *graph*) of the
edge from *current* to *i*.
- Set
*c* equal to *cost[i]*
(the cost for connecting node *i* to the spanning tree).
- If
*w* < *c* then do the following:
- Set
*parent[i]* equal to *current*.
- Set
*cost[i]* equal to *w*.

- Sort the elements of
*pq* according to the value obtained, for
each element *x* of *pq*, by calculating *cost*[*x*].
Set *pq* equal to this sorted array.

- Return the array
*parent* as the final result.

Consider the graph represented by the Ruby expression (where
`inf` was previously set to `1/0.0`):

[[0,8,inf,inf,4],
[8,0,3,inf,6],
[inf,3,0,9,5],
[inf,inf,9,0,7],
[4,6,5,7,0]]

- On paper draw the graph represented by this matrix.
- On paper, trace the execution of applying the minimum spanning
tree algorithm to the graph described by the matrix above.
- What are the final elements of the
*parent* array?
- What do those elements mean? Draw the resulting tree on paper.

### Deliverables

Hand in the paper with your work.