Computer Science 302
Introduction to Data Structures
Spring 2005
Assignment 4

Due Tuesday, April 5, 2005.

• 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 would 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 capitol city on an island.
  A certain island has one city, which is the capitol, 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 capitol 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 for Marinduque
    • Actual Map of Marinduque
    • Acceptable Output for Marinduque
  • Input files needed. Run your program on the following two input files:
    • Assignment input for Molokai
    • Actual Map of Molokai
    • Assignment input for Ireland
• Documentation will be a requirement for this assignment:
  • A design document is optional.
  • 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'' CSC 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.
• As always, the programs must be executed on our machine, "student".
  If you cannot get your program to run on that machine, even though it works on some other computer, that will be graded the same as non-working code, in other words, partial credit might be given.
• Turn in all files, including a file that shows several sample runs.
  All files must be turned in electronically to the teaching assisant. The deadline for electronic submission is Tuesday, April 5. The submission must be timestamped before midnight. You must mail it from your engineering college account.
  Be sure to include the string "CS 302 001 Hw4" in the subject field of your email.