Assignment 9, due Apr 1

Solutions

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

  1. Background: Look at the test data distributed for MP4. This test data has a clock neuron that "ticks" once every time unit, and a count neuron that "counts" clock pulses and eventually turns off the clock. The key line in this simulation model is: 
    synapse - CLOCK COUNT 0.5 7.0

    Also recall the formula for voltage as a function of time at a neuron,

      v2 = v1et1–t2 + s

    and note that you know the time interval t1–t2 and you know that for the counter to eventually fire, v2 must be greater than v1.

    A Question: What is the minimum value of the strength of this synapse for which the simulation will terminate. You can, of course, do this empirically if you have a working simulation, but it is also a straightforward math problem at the level of a pre-calculus course. (1 point)

    Treating this as a math problem, we need to find the value of the strength s for which v2 equals v1. If the actual value of v1 is less than this, it will rise asymptotically to this value, if it is less, it will fall asymptotically to this value. So, to begin, solve for s such that:

      v = vet1–t2 + s

    There are too many unknowns here, but we know some of them from the setting in the neuron network. Specifically, we know that CLOCK fires once per time unit, so t1–t2=1. Therefore, we are trying to solve this:

      v = ve–1 + s

    Solve for s and we get:

      s = v – ve–1

    Simplify:

      s = v(1 – 1/e)

    Now, what is the value of v we are interested in? A value where v is just great enough to trigger COUNT. According to MP4, the threshold of COUNT is 10.0, so we want this:

      s = 10.0(1 – 1/e)

    Given that e=2.718..., this implies that the required synapse strength is at least s=6.321...

  2. Background: In lecture on Mar. 28, it was noted that Intersection.incoming and Intersection.outgoing are initialized to empty lists but no content is ever added to those lists.

    In answering the following, please refer to the code distributed on Mar. 7; this code contains everything relevant to this oversight.

    a) What method or initializer in what class has the information needed to correctly add content to these lists? (0.5 points)

    The initialier for class Road knows where the road comes from (outgoing for the source) and where the road goes (incoming for the destination).

    b) Give code to add the content to these lists. Write this code so that it could be added at the very end of the method or initializer you identified in part a. (0.5 points) 

    if (source != null) source.outgoing.add( this );
if (destination != null) destination.incoming.add( this )

    The checks for null are required because code earlier in this initializer allowed these possibilities when undefined intersections are referenced.

  3. Background: In the lecture on Mar. 25, the following code was suggested to get a uniformly distributed pseudorandom number between 0 (inclusive) and n (exclusive): 
    public static int fromZeroToN( int n ) {
	int v = stream.nextInt();
	if (v < 0) v = -v;
	return v % n;
}

    Inn class Random, a significantly more complex method that returns a very similar result is given, nextInt(n).

    a) In nextInt(n), there is a very clever trick to detect integers that are powers of two. Give the expression that does this. (This is a scavanger hunt question.) (0.5 points) 

    if ((n & -n) == n)  // i.e., n is a power of 2

    I have quoted the entire line above from the Java documentation, the expression that does this is in parentheses.

    b) The code given above is a bit faster than the Java library's nextInt(n), but it delivers a slightly non-uniform result distribution. Suppose you called fromZeroToN(5) repeatedly. Each time you called it, it would return a value from 0 to 4 (inclusive). Why are the different values not equally probable? That is, what is the problem that nextInt(n) is trying to solve? (0.5 points)

    5 does not divide evenly into 231–1 (it is a prime number); as a result, the probability of the first (or first few) values in the range 0 to 4 is slightly higher than the probability of the remaining values.

    Note: The difference is a factor of the order of (231/5 + 1)/(231/5).

    In general, if you ask for fromZeroToN(n), the probabilities of the different results will differ by a factor of about (231/n + 1)/(231/n). This is negligable for small values of n but grows to be significant as the range of values grows.