4003-541-70/4005-741-70
Data Communications and Networks II
Graduate Programming Project 2
Prof. Alan Kaminsky -- Spring Quarter 2006
Rochester Institute of Technology -- Department of Computer Science
Overview
Software Requirements
Submission Requirements
Grading Criteria
Late Projects
Plagiarism
Overview
Suppose we have a network of N nodes. The nodes are located at given (x,y) coordinates in the unit square from (0.0,0.0) to (1.0,1.0). We wish to add links between selected nodes such that:
-
The network's edge connectivity is K or greater,
where K is a given value.
- The total length of all the links is as small as possible, where a link's length is the Euclidean distance between the link's endpoints.
Write a program to find the optimal network design for a given value of K and a given list of the nodes' (x,y) coordinates in the unit square. The program must use an exhaustive search with branch-and-bound. (To learn about this technique, consult an algorithms textbook.)
The program outputs a list of the links in the optimal network as well as the total link length. The program also produces a plot of the optimal network like the one below, showing the node's locations as black circles and the chosen links as red lines.
Here is an example network with 12 nodes and K = 2:
java OptimalNet 2 0.296 0.753 0.646 0.416 0.549 0.556 0.827 0.394 0.999 0.221 \ 0.650 0.006 0.424 0.521 0.623 0.283 0.371 0.873 0.336 0.007 0.311 0.571 0.673 0.865The correct output and plot for this network are:
0-8 0-10 1-2 1-7 2-6 3-4 3-11 4-5 5-9 6-10 7-9 8-11 3.0464808289698833
Software Requirements
Requirement 1.
The program is called OptimalNet.
The program is run by typing this command:
java OptimalNet <K> <x0> <y0> <x1> <y1> ...
where <K> is the required edge connectivity,
<x0> and <y0> are the coordinates of node 0,
<x1> and <y1> are the coordinates of node 1,
and so on through node N-1.
(Note:
This means that the main program class must be named OptimalNet,
and this class must not be in a package.)
Requirement 2. The program must print an error message and must terminate if there are any of the following problems with the command line arguments. The wording of the error message is up to you.
- Any required argument is missing.
- K is less than 1.
- The number of nodes is less than 2.
- Any node coordinate is outside the range 0.0 through 1.0.
Requirement 3. The program must print the links in the optimal network on the standard output. Each line of output gives one link, formatted as follows: the smaller node number, a hyphen, and the larger node number. There is no additional whitespace before, after, or within the line. The links must be printed in ascending order of the first node number. For a given first node number, the links must be printed in ascending order of the second node number.
Requirement 4. After printing the links, the program must print one line on the standard output giving the total link length of the optimal network as a floating point number. There is no additional whitespace before or after the line.
Requirement 5. The program must display a plot of the optimal network, formatted as shown above, using the plotting classes from the Computer Science Course Library. The X and Y axis length is 500. The node circle diameter is 10. The link line width is 1.
Submission Requirements
Your project submission will consist of a Java archive (JAR) file containing all the Java source files for your project.
-
Each Java source file name must end in ".java".
-
Each class or interface
must include a Javadoc comment
describing the overall class or interface.
- Each method within each class or interface must include a Javadoc comment describing the overall method, the arguments if any, the return value if any, and the exceptions thrown if any.
See my Java source files which we studied in class for the style of Javadoc comments I'm looking for.
Put all the source files into a JAR file named "<username>.jar", replacing <username> with the user name from your Computer Science Department account. The command is:
jar cvf <username>.jar *.java
If your project used classes from the Computer Science Course Library without modifications, you do not need to include the source files for these classes in your submission. If your project used classes from the Computer Science Course Library with modifications, you do need to include the source files for these classes in your submission.
Send your JAR file to me by email at ark@cs.rit.edu. Include your full name and your computer account name in the email message, and include the JAR file as an attachment.
When I get your email message, I will extract the contents of your JAR file into a directory. I will set my Java class path to include the following directories: the directory where I extracted your files, and the Computer Science Course Library directory. I will compile all the Java source files in your submission using the JDK 1.5.0 compiler. I will then send you a reply message acknowledging I received your project and stating whether I was able to compile all the source files. If you have not received a reply within one business day (i.e., not counting weekends), please contact me. Your project is not successfully submitted until I have sent you an acknowledgment stating I was able to compile all the source files.
The submission deadline is Tuesday, May 2, 2006 at 11:59pm. The date/time at which your email message arrives in my inbox (not the time when I actually read the message, which will be some time later than when it arrives in my inbox) will determine whether your project meets the deadline.
If you submit your project before the deadline, but I do not accept it (e.g. I can't compile all the source files), and you cannot or do not submit your project again before the deadline, the project will be late (see below). I strongly advise you to submit the project several days before the deadline, so there will be time to deal with any problems that may arise in the submission process.
Grading Criteria
50% of your project grade will be based on the design of your project as documented in the Javadoc and as implemented in the source code. Your project should:
- Be designed using object oriented design principles.
- Make use of reusable software components where appropriate.
- Be documented using proper Javadoc style as described above.
- Correctly implement the exhaustive search with branch-and-bound.
50% of your project grade will be based on test runs of your project. The grade for this portion will be based on whether your project produces the correct data on the standard output and the correct plot as specified in the Software Requirements. Every incorrect output will result in a loss of points. There is one exception: If your application does not run using the command line stated in Requirement 1, you will receive 0 points for this portion of your grade.
Any deviation from the requirements will result in loss of points. This includes errors in the output formatting (such as incorrect number of spaces, incorrect capitalization, or incorrect punctuation), misspelled output, and extraneous output not called for in the requirements. The requirements state exactly what the output is supposed to be, and there is no excuse for outputting anything different. If any requirement is unclear, please ask for clarification.
Late Projects
See the Course Policies for my policy on extensions.
I will not accept a late programming project unless you arrange with me for an extension. A late programming project will receive a grade of 0.
Plagiarism
See the Course Policies for my policy on plagiarism.
You may use any resources you wish to do the programming project, including resources discussed in class and resources you find on your own. You may discuss the programming project at a general level with others in the class. However, the programming project you turn in must be entirely your own work. You are not allowed to collaborate with anyone else on the programming project. You are not allowed to use any current or past student's work in any way when working on your programming project.
I will not tolerate plagiarism. If in my judgment the programming project is not entirely your own work, you will get a grade of 0 for the programming project. I will also place a report of the plagiarism incident in your permanent file in the Computer Science Department office. Repeated plagiarism incidents will result in disciplinary action in accordance with Computer Science Department policy and RIT policy.
There are only two exceptions to the prohibition on plagiarism:
-
You may reuse without modification
a source file from the
Computer Science Course Library.
- You may take a source file from the Computer Science Course Library and add your own modifications, provided you state that you have done so and give credit to the original author.
| Course Page |
| Home Page |