Assignment 9

Due Mar 24, on line

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


Scores from HW9 are a problem due to a serious mistake on my part. I accidentally released the solutions at 6:42 PM Wednesday afternoon and did not discover I'd done so until around 10 PM. Students who discovered the posted solutions got perfect scores with no effort, while others found this to be a challenging assignment.

The obvious resolution to this is to simply drop the score from this assignment, but that penalizes those who didn't notice the posted solutions. The alternative is to drop perfect scores earned after 6:42 PM -- ICON keeps the date of submission to the minute. Perfect scores are sufficiently unusual on my homework/quizlets that this seems reasonable.

Simple multiple choice questions, 1 point each:

  1. Here is a bit of Java code from class Source in the code distributed with the lecture notes for March 19.
    private void create( double time ) {
    	time + interval ),
    	(double t)-> create( t )
        System.out.println( time + " created at " + this.toString() );
        // BUG: must create a vehicle

    The lambda expression in this bit of code provides the body of the trigger method of an implementation of the interface Simulator.Action. What is the implicit parameter list for the constructor for the new object passed to Simulator.schedule?
    a) ()
    b) ( t )
    c) ( this ) – correct
    d) ( time )
    e) ( this, time )

    The first step in answering this question is to identify the constructor call hidden in this line of code. A λ expression in Java does the following:

    • It defines a class that is an anonymous implementation of a functional interface, where the body of the λ expression is the body of the method required by that interface, here, the trigger method of an implementation of Action. In the following, we'll call this anonymous class Anon.
    • It calls a constructor for an instance of that class. Here, that instance is a parameter to Simulator.schedule.

    So what are the parameters to that constructor? As an inner class, the parameter list looks empty. You'd write new Anon() to create an instance. But, the body of the inner class is a method call to create, and create is not a static method. Therefore, a call to create is implicitly a call to this.create for the current object. The variable this is implicitly defined by the header to every constructor and non-static method, so to implement the inner class, it must be passed, as an implicit parameter, to the constructor. Answer c) does this.

    Several students leanded toward answer e), but time is never mentioned inside the λ expression. Rather, the simulated time is passed as a parameter to the trigger method much later, when the action is triggered.

  2. Here is a bit of Java code from class RoadNetwork in the code distributed with the lecture notes for March 19.
    Simulator.schedule( endOfTime, (double t)->System.exit(0) );

    This is rather stupid, it just kills the program, while really, we should replace the call to System.exit( 0 ) with a call to a routine to wrap up the simulation and print out a final report of the results, perhaps summary statistics of the congestion on each road and the waiting times to get through each intersection. We'll call the method that does this wrapUp. Which of the following would be the best replacement for the above line?
    a) Simulator.schedule( endTime, (double t)->wrapUp( t ) ); – correct
    b) Simulator.schedule( endTime, (double t)->this.wrapUp( t ) );
    c) Simulator.schedule( endTime, (double t)->Simulator.wrapUp( t ) );
    d) Simulator.schedule( endTime, (double t)->wrapUp() );
    e) Simulator.schedule( endTime, (double t)->this.wrapUp() );

    It's worth noting that there's a typo here, endTime and endOfTime should have been the same name, this adds a little confusion to the question, but does not change the reasoning about the answer.

    Does the proposed wrapUp method need to know th time? Nothing is said about what it does other than "print out a final report of the results, perhaps summary statistics." That is enough, really, since summary statistics frequently include such things like averages over time. Therefore, d) and e) are poor choices.

    Is the proposed wrapUp method likely to be a static method of class Simulator? Noting in that class knows about what is being simulated, therefore it would have a hard time gathering useful statistics about the model. Therefore c) is a poor choice.

    Where would this call to Simulator.schedule take place? Probably either in the main method or in a static initialization method called from the main method. If the call is in a static method, this is undefined, so b) and e) are bad choices.

  3. In the distributed solution to MP5 log-normal distributions were used in only one place in the code, to determine the unfilled capacity of each place in the method findPlace in class PlaceKind. We need many more log-normal distributions to solve MP7, so it would make sense to add support for this in class MyRandom. Which of the following would be the best (partial) header for this new method? In answering this, keep in mind that efficiency matters in simulation programs!
    a) int nextLogNormal()
    b) double nextLogNormal()
    c) int nextLogNormal( Double median, Double scatter )
    d) double nextLogNormal( Double median, Double scatter )
    e) double nextLogNormal( Double median, Double sigma ) – correct

    It's worth noting that there's a typo here, Double should have been double. That makes all of the alternatives c), d) and e) slower, but does not change the right answer.

    We can rule out a) and b) because the log-normal distribution requires two parameters.

    We can rule out a) and c) because the log-normal distribution needs to give a real-valued result (float or double in Java) in order to support log-normal distributions of things like the time of a disease state. In our older code, we used it only to compute capacities of places, rounding the result to the nearest integer, but with MP7, the general case matters.

    That leaves the choice between d) and e). We can express the log-normal distribution either way. Either logNormal computes sigma (the standard deviation of the underlying normal distribution) or we require the caller to compute it. Therefore, efficiency has to be the deciding factor. If we make logNormal compute sigma for each call, that computation will be duplicated each time a number is drawn from the distribution. If we make the caller compute sigma, we can compute it only once, saving the result and passing it each time we need to draw yet another number from the same distribution.

  4. One challenge in MP7 is keeping track of the number of people in each infection state. Suppose you use an enum InfectStates to declare the potential state values from uninfected to dead. (We assume dead is the last in the list.) Now, you can use an array indexed by infection state to keep track of how many people are in each state. Declaring this array is easy:
    int[] infectPop = new int[InfectStates.Dead.ordinal() + 1];

    Now, if a person's infection state changes from oldState to newState, you'll have to write this code to track the population change:
    a) infectPop[ oldState ]--; infectPop[ newState ]++;
    b) infectPop[ InfectStates.oldState ]--; infectPop[ InfectStates.newState ]++;
    c) infectPop[ oldState.ordinal() ]--; infectPop[ newState.ordinal() ]++; – correct
    d) infectPop[ oldState.hashCode() ]--; infectPop[ newState.hashCode() ]++;
    e) infectPop[ InfectStates.valueOf( oldState ) ]--; infectPop[ InfectStates.valueOf( newState ) ]++;

    The variables oldState and newState hold objects of class InfectStates. Therefore, they cannot be used as array indexes. This rules out a). They are not names of static components of InfectStates either (the static components are named latent, asymptomatic etc., up to dead). That rules out b).

    The hashCode() method, applied to any object, gives an integer, and integers can be used for array indexing, but the integers you get are huge and appear random, so alternative d) is unlikely to work.

    The valueOf method applying to enum classes does not do anything like what the code above seems to be implying. If you look it up, you'll see that the number of parameters supplied is just plain wrong. Alternative e) is utter nonsense.

    That leaves c). The ordinal() method of an enum gives a small integer, zero for the first member of the enumeration, one for the second, and so on. This lets us use enum constants as array indices.

  5. In the Q&A for MP7, a student asked for a really simple example, and the Q&A includes a little demo class that executes either 10 or 11 step() events before it executes the end-of-time event. To understand the source of the unpredictability of this toy program, it is useful to read the Wikipedia entry on sorting algorithms. Which of the following explains the instability?
    a) The sort used by Java priority queues is an in-place sort.
    b) The sort used by Java priority queues is a selection sort.
    c) The sort used by Java priority queues is an insertion sort.
    d) The sort used by Java priority queues is a stable sort.
    e) The sort used by Java priority queues is an unstable sort. – correct

    How the sorting is actually done is irrelevant. Are object moved from here to there, or is the sorting dne in place. Do we sort by selecting the least element when we do remove from a queue or do we sort by keeping things in order whenever we do add to a queue. FIFO queues can be made both ways. So, a), b) and c) are irrelevant.

    What matters is, does the queue preserve the order of elements with equal keys. In our case the last midnight report was scheduled at exactly the same time as the end-of-time event. Which happens first. That is a question of the stability of the sorting algorithm. It happens that class PriorityQueue uses a heap data structure, according to the Oracle documentation for the class. That is the exact same data structure underlying heapsort, a very high performance but unstable sorting algorithm.