CS:2820, Homework 4 solutions, Fall 2017

Background: Consider the following two Java code fragments. Rewrite each of them a while loop instead of a for loop. (0.5 points each)

System.out.println( "Start" );
for (int i = 1; i < 10; i++) {
    System.out.println( "i = " + i );
}
System.out.println( "End" );

System.out.println( "Start" );
{
    int i = 1;
    while (i < 10) {
        System.out.println( "i = " + i );
        i++;
    }
}
System.out.println( "End" );

for (Road r:roads) {
    System.out.println( r.toString() );
}

{
    Iterator  it = roads.iterator();
    while (it.hasNext()) {
        Road r = it.next();
        System.out.println( r.toString() );
    }
}

Background: There are always alternative solutions to any programming problem. The code suggested in the notes keeps the list of all roads and all intersections in the main program's class. We could have had class Road keep the list of all roads, and class Intersection keep the list of all intersections. Assume we want to do this, and that we make these lists private. This suggests that class Intersection should export a static method for looking up a road by name instead of having this search method in the main class..

a) Give an appropriate declaration for the list of roads inside class Road. (0.3 points)

private static LinkedList  roads = new LinkedList  ();

Strictly speaking, the initial value (every thing after the equals sign) is not required by this question.

b) Give the code you would use inside the Road constructor so that the constructed road automatically adds itself to the list. (0.3 points)

roads.add( this );

c) The main class still needs to iterate over all the roads in order to print out the textual representation of the road network. Suggest how class roads could permit this without exporting the list itself. (0.4 points)

One solution is to put a print-roads public static method in class Road that prints all the roads.

Another solution is put a road-iterator public static method in class Road that returns an iterator over the private variable roads.

There are, of course, other solutions.

Background: Consider the problem of designing test data to test the linear search version of findIntersection given in Lecture 7, using a path-testing methodology.

a) Identify all of the distinct paths through this code. (0.5 points)

Finds the intersection with no iteration (iters not empty, first item is a hit).
Finds the intersection with least one full iteration (iters contains at least 2 elements, first item is a miss).
Reaches the end of the list without finding the intersection (iters contains at least 1 element, no hits).
Empty list (iters contains no elements).

The adequacy of the above solution is fairly obvious. Note that there are 2 boolean tests in the control structure, one testing for loop termination and one testing for a hit or miss. With 2 booleans, there are 4 possible combinations of true and false, so it should be no surprise that we found 4 paths. This does not mean that there must be 4 paths; in fact, we can actually execute each statement at least once with just 3 paths:

Finds the intersection with no iteration (iters not empty, first item is a hit).
Uses at least one full iteration, regardless of how it returns (iters not empty, first item is a miss).
Empty list (iters contains no elements).

b) Describe how you could test these paths using input to the road-network program. Merely giving the input file(s) is not sufficient without an explanation of how what each input file or each input line tests. (0.5 points)

intersection i -- searches an empty list to see if i already defined
road i j       -- searches for and finds i, fails to find j

That's actually a sufficient test!

Assignment 4, due Sep 15

Solutions