Assignment 6, due Oct 9

Solutions

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

  1. Background: In the assignment for MP2, consider the problem of adding a test for logic circuit completeness to the code distributed to the class as a solution to MP1. In that code, each gate has a field called inputList that contains the names of the inputs of that gate that have not yet been used.

    a) Suggest complete code for an isComplete() method you could add to the class gate to test whether the inputs to that gate were completely defined. Don't bother with comments, the whole method is only 3 lines of code (with a large number of possible middle lines). For this part, assume no other parts of MP2 are to be solved. (0.5 points) 

    boolean isComplete() {
	return inputList.isempty();
}

    b) Now, suppose we used the ordinal position of the input name in inputList in order to compute the corresponding input number. Explain (briefly) how this idea is in conflict with the version of isComplete() discussed above. (0.5 points)

    If we make deletions from inputList, the ordinal position of the surviving list elements will change when each item is deleted, so the ordinal list position does not uniquely identify the input name.

    c) Suppose we make inputList read-only (that is, we never change any attributes of inputList after it is initialised. This lets us use the ordinal position of a list element as the input number, but it prevents us from keeping the implementation of isComplete() from MP1. Suggest, briefly in no more than one or two sentences, an alternative implementation of isComplete(). (0.5 points)

    We could initialize an array of booleans to false for each input, and then, as each input is used, set the array entry to true. The gate inputs are completely wired when all the array elements are true.

    d) Does the final keyword, applied to the declaration of inputList() prevent accidental modification that would violate the constraint on which part c) above is predecated? (0.5 points)

    No, final just prevents changing which object is attached to the field. It does not prevent changes to the value of the object.

  2. A short question: In the code distributed to the class as a solution to MP1, consider the fields of class Wire. Are there any of these fields that cannot be marked final? Hint: You could just try it and see what happens. (0.5 points)

    None of them can be final, as it turns out. Apparently the Java compiler is not smart enough to figure out that each of these fields is assigned exactly once in scan().

    In principle, it should be possible to declara all of these fields to be static, but the Java definition requires that final variables be initialized in the object constructor, not outside of that constructor.

    (Students who didn't try it but understood that all of these variables are in-fact assigned just once should get partial credit -- those who said some could and some could not would be clearly wrong.)

    If you want to make the fields final, you'd have to defer initialization until you know all their values, and then call the initializer. This is an interesting exercise, worth assigning later.

  3. A short question: In the code distributed to the class as a solution to MP1, there are comments saying: No outside code uses the default initializer. As it turns out, Java includes a mechanism that solves this problem, you can declare an initializer to be private. Write the private initializer for class Gate that prevents any code from outside of class Gate from using the initializer new Gate(). Hint: It is no more than 2 lines of code. (0.5 points) 
    private Gate() { }

    This code seems silly -- it seems to do nothing. In fact, what it does is declare the initializer to be private while providing no new behavior beyond the default initialization of all fields.