Assignment 9, due Oct 27

Solutions

Part of the homework for CS:2820, Fall 2017
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: At the end of the notes for Oct. 24 (Lecture 18), simulation code is presented for intersections protected by a stop light, and a question is posed: Which of the following two alternative traffic laws does this code model:
    1. When the light turns green, all vehicles currently stopped waiting for that light may continue, even if the light turns red before all waiting vehicles have left.
    2. When the light turns red, vehicles may not enter the intersection, without regard to how long they have been waiting.

    a) Which law does the code simulate. (0.4 points)

    The second. As soon as the light changes to red, waiting vehicles must stop. Only the vehicle actually in the intersection is allowed to continue.

    b) One line of the given code is the key to the above conclusion. In what method is that code and what line is it? (0.6 points)

    The method is StopLight.departureEvent. 

    // if there are more vehicles, schedule the next departure
// in effect, departure events are a process that drains the queue
if (queues[lightDir] > 0) {

    I quoted the line of code with its comments here. The key is, lightDir may change between departure events, so with each departure event, we look at the current light direction, without regard to its history.

  2. Background: Consider using the class hierarchy from the posted solution to homework 8 as part of a logic simulator. (you are welcome to correct the class name TwoOutGate to be TwoInGate.) The logical names for the event-service routines of gates in this context are inputChangeEvent and outputChangeEvent.

    When an input change event occurs, the new value of the input that changed is recorded and then, if the result is a change in the output, an output change event is scheduled one gate delay later.

    When an output change event occurs, the list of wires connected to the corresponding output is traversed to schedule input changes at the far ends of that wire one wire delay later.

    In each part of the question below, you could define a distinct version of the event service routine for each concrete class at the leaf of the class hierarchy, or you could move code up the hierarchy.

    a) Where in the hierarchy would be the best place to define versions of outputChangeEvent? Equivalently, which leaves of the class hierarchy can share the same versions of outputChangeEvent? (0.5 points)

    All logic gates have just one output, so we can define one version of outputChangeEvent in class LogicGate.

    Class ConstGate requires its own version of outputChangeEvent; this applies only to the true output and is scheduled exactly once per constant gate, at start-up.

    b) Suppose inputChangeEvent directly computes the new output. Where in the hierarchy would be the best place to define versions of inputChangeEvent? Equivalently, which leaves of the class hierarchy can share the same versions of inputChangeEvent? (0.5 points)

    We'd have to put one version of inputChangeEvent in each of the classes AndGate, OrGate, NotGate, and ConstGate (this last one is trivial, all it would do is output an error message).

    c) How would your answer to part b change if you added a method NewOutput to each gate, so that inputChangeEvent calls NewOutput to see if a change to the output should be scheduled. (0.5 points)

    In this case, we can have one version of InputChangeEvent in class TwoInputGate, another in NotGate, and of course, a trivial one in ConstGate.

    d) For each method discussed in parts a–c above, must that method be public, could it be private? could it be protected? (0.5 points)

    All variants on InputChangeEvent must be public (or default -- we have not really distinguished public from default access rights), since they are called from class Wire.

    ConstGate.OutputChangeEvent can be private, since it can be scheduled by the sanity check or constructor code for that class.

    NotGate.OutputChangeEvent can be private, since it is scheduled by NotGate.InputChangeEvent.

    LogicGate.OutputChangeEvent must be protected, since it is scheduled by input change events in subclasses.

    TwoInputGate.OutputChangeEvent must be protected, since it is scheduled from the versions of NewOutput in each subclass.