Lab 5: Generics and Subtyping

1. Comparable Unbounded Natural Numbers

   The natural numbers have a natural ordering: 0 < 1 < 2 < 3 < … . Modify your BigNatural interface to extend the Java Comparable interface and to reflect this natural ordering. Update accordingly: the Javadoc for BigNatural, the implementation SlowBigNatural and its Javadoc, and the JUnit test cases for this component.

   Your submission for this part of the lab should include:

   • BigNatural.java, the modified interface.
   • BigNatural.html, the Javadoc for the modified interface.
   • SlowBigNatural.java, the modified class (implementing the interface including comparison).
   • SlowBigNatural.html, the Javadoc for the modified class.
   • BigNaturalTest.java, a JUnit test fixture testing your component.

   Note that your submission should be built on top of your solution for Lab 4. That is, your component should be immutable and should include the documentation and testing you had for Lab 4.

2. Subtyping

   A system for allocating season football tickets is being designed. There are three kinds of patrons: the general public, students, and faculty. The following interfaces have been proposed to model these patrons: Person, Student, and Faculty.

   Given the similarity in behavior between these different types, it is natural to ask whether a subtyping relationship exists. For each of the following statements below concerning a potential subtyping relationship, indicate whether the statement is true or false.

   1. Student is a subtype of Person.
   2. Faculty is a subtype of Person.
   3. Student is not a subtype of Faculty
   4. Faculty is not a subtype of Student

   For each of these four statements, justify your answer. If you believe a subtyping relationship does exist, provide a convincing argument why this is the case. If you believe a subtyping relationship does not exist, provide a counter-example in the form of client code that is correct with respect to the proposed base type but broken with respect to the proposed derived type.

   Finally, if you did not answer "true" for all four statements, modify the three interfaces so that: (i) all four statements are true, and (ii) the modification is as "small" (in some rough, informal sense) as possible. (This last condition is simply to rule out a modification that establishes the subtyping relationships trivially by completely overhauling the interfaces. Do not worry about identifying the absolute smallest modification, just try to preserve the rough intent of each interface as much as you can.)

3. 100 Prisoners and a Light Bulb

   Consider the following, somewhat famous, puzzle:

   There are 100 prisoners in solitary cells. There is a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Every day, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is true, all prisoners are set free. However, if the assertion is made and it is false, all 100 prisoners are shot. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?

   There are many strategies for solving this puzzle. Your task is to write a simulation engine that evaluates a strategy. That is, the simulation tests a strategy to see how long (ie how many days), on average, it takes for a prisoner to announce that they have all visited the common room. Your simulation engine should also detect if the strategy results in an erroneous announcement being made (ie a prisoner claiming prematurely that everyone has visited the common room).

   We do not know what strategies will eventually be developed and will have to be simulated. In order for a strategy to be evaluated by your engine, however, we require that it extend the abstract base class Prisoner, which uses the LightBulb class.

   Your submission for this part of the lab should consist of a single class called Warden that contains (at least) a main method. Running this class results in the creation of the jail (ie 100 prisoners and 1 light bulb) followed by repeatedly randomly selecting a prisoner for the common room. The simulation ends when a prisoner claims that everyone has visited the room. For statistical significance, you should conduct several trials for any given strategy.

   Some specific requirements on the structure of your Warden implementation are:

   • It includes a publicly visible constant (Warden.SIZE) that represents the number of prisoners in the jail.
   • It can be reused with any particular strategy (ie any extension of Prisoner) by changing at most 1 line of code in Warden.

   (Aside: You are also provided with several sample "solutions" (Brave, Timid, and AsynchCon). Your Warden implementation should at least be tested with respect to these strategies. If you like, you can also come up with and submit your strategy in the form of an extension to Prisoner, although such a submission is not a graded part of this lab.)