CS 200 Fall 2008 Programming & Written Assignments

Programming & Written Assignments Fall 2008

Written Assignments

All written assignments should be done individually.

Homework 1: Grammars is due September 9 by 9:30AM (before start of lecture)

Questions and Answers:

What exactly do you want us to show for the execution stack? Can we just take a screen shot of running your code in Eclipse?
No to the second question. For the first... I want you to write/construct a brief description of everything on the execution stack each time a change (push or pop) is made to it, i.e., when a new method is invoked (push) or a method completes and returns to the calling method (pop). You can use my code to help in answering this question, but it does not print out exactly what you need.
Homework 2:Complexity is due September 30 by 3:00PM (delivered to Prof. Howe)
Homework 3:Trees is due October 28 by 9:30AM
Homework 4:Graphs is due November 20 by 9:30AM

Programming Assignments

The first programming assignment will be done individually. Other assignments will be done as part of teams.

Programming Assignment 1: Introduction, Review and Linked Lists due September 5 at 3:00PM

A tar file with the test cases and correct outputs is available here. Note that there is no input file test13 because test case 13 was testing your program's behavior if the input file was not found.
Questions and Answers:

Can we do a doubly linked list instead of a singly linked list?
OK.
Can we use code from a previous class for the linked list?
Yes... provided that it is YOUR code, not code given by a GTA in a previous class, not code out of the previous text, not code found on the Internet, not... well, hopefully, you get the idea.
Can we define our own exceptions?
No. Your output needs to match ours *exactly*.
What if the input file cannot be read?
The File constructor throws a FileNotFoundException by default; your code should catch it and print "File NAME cannot be found." where NAME is the name of the input file.
Hey, I think the code design could be improved by doing ... So can I do it that way instead?
Probably not. The design of the code for this assignment (and indeed all the assignments) could certainly be made more efficient, more OO, better following the recommendations of the Java designers, ... The assignments are intended to satisfy multiple objectives (pedagogical, difficulty level, dovetailing with what is yet to come, expediting grading, ...) and so sometimes will represent compromises. We have a good reason (usually!) for what we have put in the spec, which we may or may not want to tell you now :-) You are free (within reason, please!) to make suggestions, but at some point we may say "because that's the way it is." If that doesn't help, consider this Dilbert cartoon.
How can I submit my assignment?

Using checkin. The checkin command for this class is ~cs200/bin/checkin. The assignment name is PROGRAM1. To check in your assignment, the command is ~cs200/bin/checkin PROGRAM1 <assignment files>.
Programming Assignment 2: Parsing, Stacks and Teams due September 26 at 3:00PM

A tar file with the test cases and correct outputs for program 2 is available here. Note that there is no input file test10.txt because test case 10 was testing your program's behavior if the input file was not found. An explanation of the grading criteria is here.
Questions and Answers:
Should both students of a team submit the assignment?
No. The person whose last name comes first alphabetically should submit. Do not submit multiple times as we will only grade one.
Do we have to use an array to implement the queue?
Yes. You should view the assignment description as requirements not suggestions!
Do you mean by implementing stack and queue based on a linked list and an array that we need to write the methods push, pop, peek, etc using a linked list commands inside those methods and enqueue, dequeue, peek, etc using array's stuff ?

Yes, this interpretation of the assignment is correct.

In the specifications for programming assignment 2, it says to have an array-based implementation of the queue. I implemented the queue using a circular array like you had in your lecture notes. Is that okay?

That's just fine.

it says that the prog2 class should close the file after the file has been read and processed. I used a Scanner to read the file and then after the Scanner was done, I called 'close' from the Scanner class. Is that what you wanted or did you want something else?

That will satisfy the requirements.

With the destination address for IPv6 and IPv4 if there were any possible invalid values given that they are already are in Hexdecimal?

No, we'll allow for any hex combination.

Are there any invalid values for the traffic class given it is in Hex as well?

No, not at this time.

Are we required to throw stack exceptions? Is it acceptable to throw Stack Exceptions? Can I use the Stack Exception class provided for us in the last lab, or do I need to write my own?

Yes. Yes. No, you need to write your own that throws an appropriate message, and it needs to be caught somewhere as well.

In the last lab a StackInterface class was provided, my Stack class does not currently implement this interface, does it need to?

No, you needn't follow the interface provided in lab.

In the assignment, it says "The first three fields convert the hexdecimal number into decimal. " Which three fields do you mean: as shown in the table or the output?

I mean the output example: Version, Next Header and Hop Limit.

What should I call the program for checkin?

PROGRAM2

Do we need to throw exceptions if there is no file and if the file is empty? If yes, should we print out the exception or just have the program quit?
You don't need to throw an exception for "no file"; Java will do that for you. You should catch the exception, print out the message ("File
cannot be found") and then quit.
For the empty file, that just makes for a rather boring simulation. No packets are created or added to the Router. So when the Router contents are printed, it should just print the headers as in:
```
Special traffic class:

Special next headers:

Rest:
			     
```
if the packet has any spaces/tabs in it (like in the beginning or the end), should this throw a format exception or can I keep the way I have it right now to String.trim() to avoid any errors?

Just ignore the white space. This should not cause an exception.
Programming Assignment 3: More Functionality due Sunday October 19 at 3:00PM (Note: change in due date, late period ends October 21 at 3:00PM)

A tar file with the test cases and correct outputs for program 3 is available here. Note that there is no input file test5A.txt because test case 5 was testing your program's behavior if the input file was not found. Feedback can be accessed with the command ~cs200/bin/grade PROGRAM3

PA3 Test Case Regrading:
Performance on test cases was 45 points of the PA3 grade. If you are unsatisfied with your program's performance on the test cases, you may submit another version by Thursday, October 30, 3:00 PM to have the test cases regraded. I (John) will grade your new submission on the test cases only, and will award your group half the difference between your old score and the new one. This can only help you; if your new submission performs worse than your original, your grade will not change. Use checkin to resubmit. The assignment name is PROGRAM3RE. There is no late period for the regrade; after the deadline no submissions will be accepted.

In the routing table, can a version 4 IP address map to a version 6 address, and can a version 6 address map to a version 4 address?

Yes.

Can the name of a Router be a version 6 IP address?

Yes. The name can be either a version 4 or version 6 IP address.

When implementing exception handling, is it acceptable to add a throws ... clause to my main method to make my program compile?

No! Doing so means you have essentially given Java permission to allow your program to crash in the event that that exception is thrown. Rewrite your code with try/catch blocks so you don't need the throws clause.

Do we need to handle the case where we are missing a field: IE. timeStamp or eventType, and if so what type of message should it print.

Yes. From the assignment description "Ill formed lines should be discarded with error messages such as: FORMAT ERROR java.text.ParseException: mangled IP Address: event line discarded." Use this format, but just leave the message as event line discarded. It is impossible to know whether you are missing one or the other.

When should a packet be discarded if its hop limit reaches zero? Should it be discarded if its hop limit is zero before being decremented in the sendPacket method, or after being decremented?

The assignment specification is a little ambiguous about this, so here's the behavior we want: The packet should be discarded if its hop limit is zero after it is decremented in the sendPacket method. So if the packet has a hop limit of one initially, the hop limit will be decremented to zero when that packet is sent and it will be discarded.

Can we submit the assignment early and get feedback as to whether the TA can compile and run it?

Yes. I (John) will check the submissions at 3:00 on Saturday afternoon. Any programs that have been submitted by then will be compiled and run on the example file, and any compilation errors or crashes will be reported back to you by e-mail Saturday evening.

In the checkin program, what name should we submit the assignment under?

PROGRAM3
Programming Assignment 4: Binary Search Trees and More Simulation due Friday November 14 at 3:00PM
Extra Credit Opportunity: Create a test input file for programming assignment 4. Submit that input file, along with a file contining the output from your program, to Dr. Howe via e-mail by Noon on Wednesday, November 12. Be sure to specify how many timesteps to run the simulation for in your e-mail. Dr. Howe will run the canonical version of the assignment on your input and verify your program's output. If your submitted output is correct, and it's a test case that has not been previously submitted, you will receive five extra credit points on this assignment. Passing test cases will be posted here, along with the correct output.

Test cases are now posted. There are five event files. Each was run for two different values of maxTime. A brief description of each test case, as well as the values of maxTime, can be found in testCases.txt in the tar file.

What should the behavior be when sending a packet whose destination IP is not in the Router's routing table?

Set the next hop to null and return the packet as normal.

What is the assignment name for checkin?

PROGRAM4

How should I handle time in the simulator? Do I use "time" from JAVA? Should it stop at the time of the last event in the eventfile?

The simulator keeps its own time, starting from 0 and continuing until the termination criteria are met. Do not use "time" as our timestamps are simplistic. The termination criteria are: that either the current time is greater than the maxTime or that (nothing is left in the event file and no packets are on any of the internal structures of the routers). So in the second case, maxTime is large enough that the simulation runs out of tasks long before it would get to maxTime and so stops when all the packets have been taken off the routers.

How should I order the checking of the routers for packets?

The assignment says to order them by IP address. Practically, in this case, that is produced with an inorder traversal of your binary search tree of routers.

How should Routers be ordered when checking them?

You should use an inorder traversal over the binary search tree of Routers to define the order of checking. Here's a subtle point though... IPAddress components should be treated as Strings in the compareTo. In the compareTo for IPAddress, each part in IPV4, for example, is what is between the "."; compare each part separately and as soon as one doesn't match, return the value of the compareTo on that part in each IPAddress. So for example, "2.3.4.5" is actually greater than "100.3.4.5".

Can an IPv4 address has a field with a value of > 255?

Ick... the specs are somewhat ambiguous on this. No, if it comes from a packet; not specified, if it comes from the event file. So... we will *not* include a test case that has a field greater than 255. Hence, you have less to worry about from Dan Newman's test case.
Why does the test case for maxTime=3 have long exception messages?

because I downloaded the wrong output. Revised one is available via the assignment description.

Test cases
- Ben Weiner's input and output
- Wes Jeanette's input and output, maxTime=30
- Corey Flanigan's input and output, maxTime=0
- Mark Heim's input and output, maxTime=30
- Erik Rotaru's input and output, maxTime=30
- Dan Newman's input and output, maxTime=30
Programming Assignment 5: Graphs due Sunday December 7 at 3:00PM

General Assignment Information

Program Submission Steps: How-to guide for submitting programs. Look for the "For Students" sections.
Program Guidelines: Advice on what is required for all programs.

Last Updated: September 22, 2008

Programming & Written Assignments Fall 2008

Written Assignments

Programming Assignments

A tar file with the test cases and correct outputs is available here. Note that there is no input file test13 because test case 13 was testing your program's behavior if the input file was not found.

A tar file with the test cases and correct outputs for program 2 is available here. Note that there is no input file test10.txt because test case 10 was testing your program's behavior if the input file was not found. An explanation of the grading criteria is here.

A tar file with the test cases and correct outputs for program 3 is available here. Note that there is no input file test5A.txt because test case 5 was testing your program's behavior if the input file was not found. Feedback can be accessed with the command ~cs200/bin/grade PROGRAM3

Test cases are now posted. There are five event files. Each was run for two different values of maxTime. A brief description of each test case, as well as the values of maxTime, can be found in testCases.txt in the tar file.

General Assignment Information