Computer Science 302
Introduction to Data Structures
Fall 2007
Assignment 4
Due Tuesday, November 13, 2007.

-
Goals of this assignment:
-
To gain appreciation of applications of graph theory to real-life problems.
-
To gain skill in implementation of graphs as data structures.
-
To gain skill in dynamic construction of equivalence classes using
union/find.
-
To gain skill in documentation.
-
It is expected that students will discuss the assignments. But do
not turn in code written by another person. If that happens, both
persons are violating the ethics of this course. Representing the
work of another person as your own is plagiarism, and may result in
a disciplinary "F" in the course.
It is permissable (in this course, as this is up to the instructor)
for you to obtain ideas from other students or from other persons.
But you must type in the code yourself.
It is unadvisable for you to allow another student to have an electronic
copy of your work, as then you could unwittingly be a party to a breach
of these rules. Showing the other student a hard copy is less dangerous.
The above rule does not apply to copying files that I have made publicly
available. I expect that you will use those in their original form or
with appropriate modifications (made by just you, of course).
If you utilize code that you obtain from other sources, be sure to give
credit in a comment, such as:
// this code from website www.mit.edu/help/x13
-
Find the least cost telephone network connecting all villages to the
capital city on an island.
A certain island has one city, which is the capital, and n
villages. The Governor of the island has hired consultants from the
UNLV College of Engineering to optimally construct a data network linking
all villages to the capital city. This network will consist of
data lines, where each data line is between two villages or between
a village and the city. A village may have a router which can
connect to any number of data lines, but no routers are allowed
outside the villages or the city.
Consultants from another department, taking into account the varied
terrain of the island, have provided you with a list of costs for running
data lines between each pair of villages and each village and the city.
Using those costs as inputs, design a minimal cost network.
-
Here is a suggested outline of your work.
-
Represent the problem as a weighted graph, and the network as a spanning tree.
-
Use Kruskal's algorithm.
-
Use union/find in the most efficient manner you can. That means that
you must use path compression, and either rank or size as the criterion
for union.
-
Format of Input files.
Each input file will consist a number of lines, one for every edge
in the graph. The line will have the format ,
and there will be no spaces in the village names.
For example:
Chicago,NewYork 731
SantaAna,WestCovina 62
-
Sample Input and Output.
-
Input files needed.
Run your program on the following two input files:
-
Documentation will be a requirement for this assignment:
-
A design document.
Since we did not go over this in class, the requirements for
the design document for this assignment are minimal. One page
should suffice, and you can submit it electronically.
-
Loop invariants, written as comments, for any tricky loop.
It is a judgment call whether a particular loop needs to
have its loop invariant written. Use the ``reasonable'' test.
Would a ``reasonably competent'' CS major be helped, in understanding
your code, by seeing a comment explicitly stating this loop invariant?
You will need to have a loop invariant for at least one loop.
-
Input and Output conditions for functions, again using the ``reasonable''
test.
-
Comments explaning variables and functions whose purpose is not obvious.
-
Other comments, as appropriate. But code that is overcommented looks
silly.
There are some students who want to write every conceivable comment,
"Just to be sure." Don't do that. I will instruct the grader to
take off points for ridiculous overcommenting. You are supposed to
use your judgment, and you are to be graded on how good your judgment is.
-
All programming assignments must be
submitted electronically.
Submit them to the graduate assistant,
Swamynathan Swamynathan, by email at
swamy"at"egr"dot"unlv"dot"edu
on or before the due date.
Your email must come from your engineering college (or computer science
or computer engineering) account.
-
Turn in all files, including a file that shows several sample runs.
Be sure to include the string "CS 302 001 Hw4" in the subject field
of your email.
