Assignment 13

Simple multiple choice questions, 1 point each:

1. Consider the for loop in class MemoDemo distributed on Apr. 23:

   for (int i = 0; i < 30; i++) {
       final Lazy<Integer> b = new Memo<Integer>(a);
       a = ()-> b.eval() + b.eval();
   }
   

   This could be rewritten as follows:

   for (int i = 0; i < 30; i++) {
       final Lazy<Integer> b = a;
       a = new Memo<Integer>( ()-> b.eval() + b.eval() );
   }
   

   Both versions work. Both versions make the loop run very fast compared to the version without memoizatioin.
   a) These are equally efficient.
   b) The original is slower, it does an extra eval().
   c) The original does an extra eval() plus it keeps a useless memo.
   d) The new one is slower, it does an extra eval().
   e) The new one does an extra eval() plus it keeps a useless memo. — correct.

   It really helps to look at problem 2) first! Looking at that answer, you see that the new one does not create a memo for the final item in the list, an instance of InitA, where it calls eval on that item twice, and it creates a useless memo for the head of the list, used only once, and therefore wasting effort, when eval is called on the entire list. This corresponds to answer e). The difference in performance is miniscule but real.

2. Consider the data structure constructed by the two versions of the code given above. At the end of the loop, the variable a) holds the handle on the head element of a linked list of objects. The classes of some of these objects are anonymous, but names for these classes are given in the code with class MemoDemo distributed on Apr. 23. In these terms, the objects are from classes InitA, UpdateA and Memo<Integer> (abbreviated a bit below).

   How is the list structured in the original version of the code? The suggested answers below use the symbol => to mean "which contains a handle for the an object in the class."
   a) UpdateA => Memo => ... UpdateA => Memo => InitA — correct.
   b) Memo => UpdateA => ... Memo => UpdateA => InitA
   c) UpdateA => Memo => ... Memo => UpdateA => InitA
   d) Memo => UpdateA => ... UpdateA => Memo => InitA
   e) none of the above.

   In both versions of the code, each iteration creates one Update object and one Memo object in the same order. Therefore, c) and d) must be wrong because these imply either that the order switched halfway down the list or that the numbers of objects in each category are different.

   Each iteration of the original version of the code creates a Memo first, then an UpdateA, so the memo end up wrapping the InitA object and the head of the list, at the end of any iteration, will be an UpdateA object. Therefore, a) is correct and b) is the structure created by the new version, not the original.

3. Even with memoization, the code above is 10 times slower than the version that used int instead of Lazy<Integer>. A significant fraction of the slow down is due to the cost of autoboxing and unboxing in this expression:

   ()-> b.eval() + b.eval()
   

   Which of the following best shows what is actually being done here
   a) ()-> Integer.decode( b.eval().toString() + b.eval().toString() )
   b) ()-> new Integer( b.eval().toString() + b.eval().toString() )
   c) ()-> new Integer( b.eval().intValue() + b.eval().intValue() ) — correct.
   d) ()-> Integer.getInteger( b.eval().toString() + b.eval().toString() )
   e) ()-> Integer.decode( b.eval().intValue() + b.eval().intValue() )

   We are doing integer arithmetic, so nothing that involves toString can possibly be correct. That rules out a), b) and d).

   Integer.decode(s) and new Integer(s) do the same thing when given a string s, so e) must be wrong because the parameter expression looks like it is trying to add two integers, not concatenate two strings.

   The Integer.getInteger() method does something totally irrelevant, looking for a "system property." Therefore d) is nonsense.

   That leaves c), which is, in fact, correct.

4. Consider the problem of eliminating circular dependencies between classes A and B by creating new classes Aimp and Bimp that actually implement the methods of A and B, and by converting A and B to interfaces. At the end, we try to make Aimp depend on A, which it implements, and on B, which it uses. Similarly, Bimp depends on B, which it implements, and on A, which it uses.
   a) Yes! This always works.
   b) No, if the constructors of the original A and B call each other, it breaks. — correct.
   c) No, if non-static methods of the original A and B call each other, it breaks.
   d) No, if public methods of the original A and B call each other, it breaks.
   e) No, if private methods of the original A and B call each other, it breaks.

   Note that "it breaks" only means we fail to remove circular dependencies. A circular dependency between top-level (outer) classes cannot be formed by private methods, so e) must be wrong. Similarly, all circular dependencies involve methods that are either public or default (package local). This means that d) proposes that no circular dependencies can be eliminated, which is also false.

   Non-static methods are regular ordinary methods, the kind that permit removal of circular dependencies by having their code in classes that implement the interfaces they use. Therefore, c) is exactly wrong.

   Constructors cannot be part of an interface because you can only construct instances of a particular class. Therefore if the constructors of the two classes each have occasional need to call the constructor of the other class, the strategy outlined will not work. This makes b) the correct answer.

5. Consider a specific place in the epidemic simulator, a place where there are initially no people. At 8:00 AM, 10 people arrive, and one of them is contageous. They all take reasonable precautions, virtual face masks and social distancing, so the transmissivity of the place is low. Everyone leaves at 8:01 AM. The most likely outcome is that nobody got infected during their brief contact.

   How many calls to p.infect() for various people p are scheduled as a result of the above assuming the code from the distributed solution to MP11 is used?

   Make has a special case to detect and deal with circular dependencies like the above. What would happen here if it did not have this special case?
   a) 9
   b) 10
   c) 18 — correct.
   d) 20
   e) some other number.

   When the infected person arrives at the place, calls to infect() will be made for every person already in that place, scheduling an infection event at a finite future time for everyone already there. When the remainder of the people arrive, each one will check with the place, find that there is someone there who is infected, and schedule an infection event at a finite future time. The only one who does not schedule such an event is the already infected person. So a total of 9 events are scheduled.

   On departure from the place, similar logic is followed, except that the new infection events are scheduled at an infinite future time. So again, 9 events are scheduled, bringing the total to 18, 9 at finite future times, 9 at infinite future times.