Assignment 14

Due Nov 3, on line

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

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. The loop does only 39 iterations, yet it takes several seconds to print the result.

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

  1. What data structure is j by line 9 above?
    a) A simple linear list.
    b) A linear list where each item but the last two has a next pointers and a pointer that skips the next item.
    c) A balanced binary tree.
    d) An unbalanced binary tree where one subtree of each item is one deeper than the other subtree.
    e) A binary tree where one subtree of each item is twice the depth of the other.

  2. We can improve the performance by adding new Memo() surrounding the right-hand sides of lines ...
    a) 3 and 4.
    b) 5.
    c) 6.
    d) both a) and b) are correct.
    e) all of a), b) and c) are correct.

  3. There are some stupid errors in class Person in the posted solution to MP10. These don't break the program, they just make it inefficient. Consider just the variable deathProb and ignore the question of initializing it from the model description file.
    a) it should be private.
    b) it should be static.
    c) it should be private and static.
    d) it should be final.
    e) it should be private static and final.

  4. There is a comment in class Place in the posted solution to MP10 saying that the constructor for Place is effectively protected. This is true because ...
    a) Place is in an abstract class.
    b) the constructor has parameters of protected types.
    c) the constructor is not marked as public.
    d) the constructor references private fields like allPlaces.
    e) the comment really means we should write code as if it was protected.

  5. Before even thinking about eliminating dependency cycles in the Epidemic model, we need to find them.
    a) classes Person and Place are in a cycle.
    b) class Place is in a cycle with its subclasses.
    c) class Person is in a cycle with its subclass.
    d) both a) and b) are true.
    e) both a) and c) are true.

Machine Problem 12 -- due Monday, Dec 7

Rewrite and submit class, Person from MP10 (and no other class) so that it does not use inner classes for scheduling new events. As the code exists in the posted solution, all of the calls to Simulator.schedule are immediately preceeded by the definition of a local inner class for the event that is being scheduled. Your job is to move these all to the outer nesting level.

Submit one file, on line. This file should contain one public class, Person plus as many other (outer) classes as you need for all the events that need scheduling, each declared as just a class, not a public class.

This job is almost mechanical, but consider the problem of making things readable. You may find that several of the new outer classes are essentially identical except for the values of the parameters to their constructors. Feel free to combine them, but also note the importance of comments to link each new outer class to the place where it is used.

Obviously, you should put all the new outer classes together and not put some before Person and some after. This may will have consequences on the header comments on the whole file. Readability is crucial.

And, of course, the changes you make should not break anything. Working through the file one inner class at a time would make excellent sense, testing after each is moved to the outer level.