CS 330 – Spring 2018, Assignment 3
Problems due by 11:59PM on Thursday, February 22
Please submit all homework problems as a single PDF, H3.pdf, on gradescope.
Please submit the team programming assignment as H3Team.pdf, on gradescope.
Problem 1 (10 pts). Chapter 4, Exercise 24, on p. 200. Provide a greedy algorithm to solve this problem, ideally
in linear time in the size of the tree. You need to argue for the running time and prove that your algorithm gives a
correct solution that minimizes the sum of the added edge lengths.
Problem 2 (10 pts). Chapter 5, Exercise 1, on p. 246.
Problem 3 (10 pts). You have a friend who wants to drive from Boston to San Francisco, visiting his parents in
Dallas on the way, using only the interstate highway system (i.e. on roads like I-95). Unfortunately, he finds driving
long distances boring and doesn’t want to fall asleep at the wheel. He feels that he is most likely to fall asleep on
road segments that he has driven on in the past, so he wonders: is there a way to do the drive only on road segments
that he has never driven on before? You may assume that your friend has a good online road atlas listing all the
junctions and interstate segments between the junctions in the US, such as the 15-mile segment of I-90 between
Newton, MA (I-95) and Westborough, MA (I-495). He also recalls exactly which of these segments he has driven on
before.
(a.) Model this problem as a problem on graphs, and give an efficient algorithm to answer this question. You
may use standard graph data structures and graph algorithms in class as subroutines without further elaboration.
Demonstrate correctness and give a running time.
(b.) He finds that no such route exists, i.e., he cannot find a route to Dallas then San Francisco that avoids all
roads he has driven on before. So he wants to do the next best thing, find a Boston to Dallas to San Francisco
that minimizes the amount of driving on already-driven-on road segments. Give an efficient algorithm to solve this
problem. Demonstrate correctness and give a running time.
Problem 4 (10 pts). Chapter 4, Exercise 19, on p. 198.
Problem 5 (20 pts). In this programming problem, we will be considering MSTs on complete, undirected graphs.
A graph with n vertices is complete if all possible n2 edges are present in the graph. Consider the following two
types of graphs:
Complete graphs on n vertices, where the weight of each edge is a real number chosen uniformly at random
from [0;1].
Complete graphs on n vertices, where the vertices are points chosen uniformly at random inside the unit
square. (That is, the points are (x;y), with x and y each a real number chosen uniformly at random from
[0;1].) The weight of an edge is the Euclidean distance between its endpoints.
Your goal is to determine how the average weight of the minimum spanning tree grows as a function of n for
each of these families of graphs. You will need to implement an MST algorithm and procedures that generate the
appropriate random graphs. Run your program on at least five random graph instances for
n = 16;32;64;128;256;512;1024;2048;4096;8192
and report the average for each value of n. For each family of graphs, generate an appropriate figure that depicts
your results. Clearly label the axes and think carefully about the most effective representation (should it be a bar
chart, line chart, scatterplot, etc.). Also, interpret your results by giving (and plotting) two sample functions that
characterize each of your depicted results. For example, your answer might be f(n) = 2logn, f(n) = 1:5pn, etc.
Also, provide a few sentences of intuition for why the growth rate of your functions f(n) are reasonable. Do this for
both types of graphs separately.
You may work in teams of up to three people for this problem. Each team must submit one hard copy of their
code along with one joint writeup for this problem in Gradescope. Only one team member should submit – we will
ensure that all named team members get credit.
Boston University 1