Introduction
Requirement
/ CMPUT 201 Assignments /
/ Dues: /
/ #2: 11:55pm, November 13, 2017; /
/ #3: 11:55pm, December 8, 2017 /
(Mandatory assignment cover-sheet; without it, your work will not be marked.)
Submitting student:
Collaborating classmates:
Other collaborators:
References:
Regardless of the collaboration method allowed, you must always properly acknowledge the sources you
used and people you worked with. Your professor reserves the right to give you an exam (oral, written,
or both) to determine the degree that you participated in the making of the deliverable, and how well
you understand what was submitted. For example, you may be asked to explain any solution that was
submitted and why you choose to write it that way. This may impact the mark that you receive for the
deliverable.
So, whenever you submit a deliverable, especially if you collaborate, you should be prepared for an
individual inspection/walkthrough in which you explain what every line of assignment does and why you
choose to write it that way.
1
/ CMPUT 201 Assignment #2 /
/ Due: 11:55pm, November 13, 2017; /
In Assignment #1, your program can successfully read in an input file that describes NUM PT points in
the two-dimensional plane, within the rectangular area [0,MAX X] × [0,MAX Y]. E.g.,
>myprogram -i instance10 001.txt
Assignment #2 needs this functionality to continue on. (If you wish, you may purchase a workable program
from your TA, at 2 marks.) In the following, we let n = NUM PT and these n points be denoted as
p i = (x i ,y i ), for i = 0,1,…,n − 1, in the order they are read in from the input file.
For each pair of points p i and p j , the distance between them is defined as d(i,j) = |x i −x j |+|y i −y j |.
The goal of Assignment #2 is to compute a minimum-weight spanning tree (MST) for these n points,
using any data structures as you wish. The following list contains the specifications for Assignment #2
(10 marks in total), which essentially is a version of Prim’s algorithm that grows an MST from the root:
1. Choose p 0 = (x 0 ,y 0 ) as the root, and print to the output (which is either stdout or the output file
in the command line) the following line:
Choosing point 0 as the root …
2. We use a color scheme to indicate whether a point is in the tree (black) or outside the tree (white).
Initialize the tree to be empty; color the root black; every other point is colored white, and has
parent -1 (-1 stands for “no parent”).
3. Calculate the distance d(0,i) for all i = 1,2,…,n−1; this distance, now denoted as d i , is called “the
distance from point p i to the tree”, and p i now has parent 0; print the result to the output, one in a
line (the i and the d i to be replaced by their respective values):
Point i has a distance d i to the tree, parent 0;
Append a comment line to the input file, also print the line to the output:
#Edges of the MST by Prim’s algorithm:
(Remark: Your program prints the line to two data streams.)
4. Among all white points, find those achieving the minimum distance. Since there could be multiple
points achieving the minimum distance, we will select one as follows (if there is only one point
achieving the minimum distance, then the selection process is not executed, proceed to item 5):
Assume the two white points p i ∗ and p j ∗ both achieve the minimum distance, d i ∗ = d j ∗ , and their
parents are i and j (black points p i and p j ) respectively. We select the point p i ∗ ,
1) if the y-coordinates satisfy |y i ∗ − y i | > |y j ∗ − y j |,
2) or if |y i ∗ − y i | = |y j ∗ − y j | and the x-coordinates satisfy max{x i ∗ ,x i } > max{x j ∗ ,x j },
3) or if |y i ∗ − y i | = |y j ∗ − y j |, max{x i ∗ ,x i } = max{x j ∗ ,x j }, and i ∗ ≤ j ∗ .
5. Select only one white point achieving the minimum distance using the above item 4, and denote this
point as p i ∗ (its parent is i, that is, d i ∗ = d(i,i ∗ )):
1) add the edge {p i ,p i ∗ } to the tree; print to the output the following line, also append the line to
the input file (the i,i ∗ and the d i ∗ to be replaced by their respective values):
i i ∗ d i ∗
2) change the color for the point p i ∗ to black;
3) for each white point p j , if d(i ∗ ,j) < d j , then update d j to be d(i ∗ ,j) and update its parent to
be i ∗ ; if d(i ∗ ,j) = d j , then using the selection rules in item 4 to update the parent of p j (that
is, the old parent of p j might be replaced by the new parent i ∗ ).
6. Repeat the above items 4 5, until no white point exists.
2
7. Print to the output the following line, where the length is the total length of all the edges added to
the tree (the length to be replaced by its value):
The total length of the MST is length.
(Remark: Your program prints this line only to the output data stream.)
//End of Assignment #2.