Assignment 14

Simple multiple choice questions, 1 point each:

Consider this little code fragment to compute the 40th Fibonacci number. The code uses class Lazy distributed with the notes for Nov. 19.

/* 0 */  Lazy<Integer> i = ()-> 0;
/* 1 */  Lazy<Integer> j = ()-> 1;
/* 2 */  for (int x = 1; x < 40; x++) {
/* 3 */      final Lazy<Integer> ii = i;
/* 4 */      final Lazy<Integer> jj = j;
/* 5 */      i = j;
/* 6 */      j = ()-> ii.eval() + jj.eval();
/* 7 */  }
/* 8 */  System.out.println( "= " + j.eval() );

The loop does only 39 iterations, yet it takes over a second to output the result. If we use class Memo (see MemoDemo.java distributed with the April 23 lecture notes), we can do better (or worse).

1. Line 6 above can be rewritten several ways. Consider the following two alternatives:

   j = new Memo<Integer>( ()-> ii.eval() + jj.eval() );
   j = ()-> new Memo<Integer>( ii ).eval() + Memo<Integer>( jj ).eval();
   

   How do these compare?
   a) The second is slower because it creates too many memos.
   b) The first is slower; it creates its memo too late to do any good.
   c) The second is slower; each memo is forgotten after one eval(). — correct
   d) The first is slower because it does not create enough memos.
   e) They do essentially the same thing.

   They both work, but if you try them, the performance is radically different. The second one is as slow as not doing any memoization. So, empirical arguments rule out b), d) and e).

   Looking at the code, the key thing to notice is that the second alternative memoizes ii and jj inside the λ expression. This means that each memo is used immediately after it is created, and no memo will ever be remembered and referenced again. That sounds like c), and it clearly rules out b), d) and e).

   In a sense, a) does describe the truth, but see the next problem for an alternative solution that creates just as many memos as the second alternative here but runs just about as fast as the first alternative. The central issue here not so much how many memos are created, but how effectively they are used.

2. Consider the following two changes, we could rewrite lines 3 and 4 like this:

   final Lazy<Integer> ii = new Memo<Integer>( i );
   final Lazy<Integer> jj = new Memo<Integer>( j );
   

   Or we could rewirte line 6 like this:

   j = ()-> new Memo<Integer>( ii ).eval() + Memo<Integer>( jj ).eval();
   

   How do these compare?
   a) Rewriting 6 is faster because it makes all the memos in one place.
   b) Rewriting 6 is slower because memo creation is deferred. — correct
   c) Rewriting 6 is faster because it avoids redundant eval() calls.
   d) They build different data structures, but the performance is identical.
   e) They do exactly the same thing.

   Rewriting 6 is slower for the reasons outlined in the solution to the previous problem, so a) and c) are wrong. The same arguments rule out d) and e) because the performance difference is huge.

   Rewriting 6 defers memo creation until the eval() method passed by the λ expression is called, making b) the right answer. At that point, it is too late to do any good. The values computed by these two are the same, but the performance is not at all the same. The difference in performance rules out d) and the difference in the way they compute their values rules out e).

3. Person.die() in the code posted for MP11 had this basic outline:

   diseaseState = DiseaseStates.dead;
   location.depart( time, this );
   

   But it had this outline in MP12: MP12.

   location.depart( time, this );
   diseaseState = DiseaseStates.dead;
   

   The change was made because it fixed a bug. What were the symptoms of the bug?
   a) There was a memory leak involving dead Person objects.
   b) The count of dead people was not correctly incremented.
   c) The count of bedridden people was not correctly decremented.
   d) Dead people were still counted as being as infectious. — correct
   e) Dead people were still counted as part of the population.

   I found this problem running the simulator using testd. My first thought was that somehow, dead people were being resurrected, or at least, I'd somehow hit on how to simulate resurrection.

   The central problem turned out to be that location.depart() only decrements the count of infectious people in the place if the person is still infectious when it is called. By changing the disease state to dead before calling location.depart(), it didn't decrement the count, and the result was that places where people had died remained permanently infectious from then on. That is, answer d).

4. In the posted solution to MP12, a new method was added to class Time to scan a time from the input. This can read times in commonly used human readable formats like 10:34am or 15 days. Which of the following would it not understand correctly?:
   a) 10 : 34 : 15 pm
   b) 10:34.25pm
   c) 10 : 34 . 25 pm — correct
   d) 10.57083pm
   e) 22.57083

   This is a problem where reading the code is worthwhile. The code uses hasNextLiteral() to look for colons and suffixes like pm. This method skips leading spaces just the way the getNext methods do, so there should be no problem reading a) or b) or d) or e) — all of these refer to approximately the same time. The problem with c) is that the value 34.25 is a single floating-point value (a double), and Java's methods to interpret floating-point values do not allow spaces around the point.

5. When you eliminate a dependency loop between classes A and B by moving the implementations of the two classes into Aimp and Bimp, certain dependencies can be eliminated, but some remain. In the following, assume that for each call to something in A from something in B, there is also a similar call in the opposite direction. Which of the following kinds of circular dependencies are eliminated by this use of interfaces?
   a) calls to methods of A in methods of B. — correct
   b) calls to static methods of A in static methods of B.
   c) calls to constructors of A in methods B.
   d) calls to constructors of A in constructors of B.
   e) all of the above.

   In class, we demonstrated doing a). Note that the use of the term static in b) strongly suggsts that a) is referring to non-static methods.

   Java's class hierarchy does not allow static methods to be overridden by subclasses or given deferred implementations using interfaces. Therefore, circularity in the static methods cannot be solved by the tactic discussed here, so b) is wrong and also e) is wrong.

   Similarly, constructors must be in the implementation, not in the interface or the parent class, so c) and d) are wrong and also e) is wrong.