CS685 - Project #2 - Dependencies

Page Contents:

  1. Introduction
  2. Applet
  3. Source Code
  4. Analysis

1. Introduction

This project, due 1998-09-22, was supposed to get us thinking about dependencies between parts of a system.

proj2.html
Here's what I submitted to the teacher. I've left it as-is, so there's no navigation on it.

2. Applet

Instructions:

  1. Select a size; this will set an appropriate number of parameters to 1.
  2. Select an initialization mode.
  3. Click Start.
  4. Click Next repeatedly until the parameters are all 0.
  5. Repeat steps 1-4 until bored.

3. Source Code

depend.java (.html)
My entire program is in one class.

4. Analysis

4.1 Behavior

Let N be the number of true parameters at the start of execution. [This defaults to size (all true), but the user can edit them.]

If N = 0, the program will never go through a loop, so end time = 0, regardless of initialization mode. Therefore, when considering the behavior of the following initialization modes, assume N > 0.

a) when Dependencies is all false

Parameters[] immediately goes to all false (end time = 1), regardless of N.

Since Dependencies[index,dep] is false for every index and dep, no NewParameters[dep] ever has a chance of being set to true. When Parameters[] is overwritten with NewParameters[], it is set to all false, and so the execution terminates after one time through the loop.

b) when Dependencies is true on the diagonal

Parameters[] decays to all false in roughly log2 N turns.

Each parameter is dependent only upon itself, so every turn, each true parameter has a 50% chance of going false. Once it goes false, a parameter will never go true again, because it depends upon itself. At time 0, there are N true parameters. At time 1, there are on average N/2 true parameters. At time 2, there are N/4, etc. So, the end time is on average log2 N + 1.

c) when Dependencies is true on or above the diagonal

Parameters[] decays to all false in roughly 2N turns.

Consider the case where N=4 and Size >= 4. For simplicity, at the start of execution, assume we "shift left" each of the true parameters to fill the spots left by the false parameters. We get the same result (time wise) in the end. The following table describes the chances of a given parameter being true the following turn:

      CURRENT     # true      chance of being
       STATE      depends      true next turn
param 1 2 3 4     1 2 3 4     1    2    3    4
      -------     -------    -------------------
      1 1 1 1     1 2 3 4    1/2  3/4  7/8 15/16
      1 1 1 0     1 2 3 3    1/2  3/4  7/8  7/8
      1 1 0 1     1 2 2 3    1/2  3/4  3/4  7/8
      1 1 0 0     1 2 2 2    1/2  3/4  3/4  3/4
      1 0 1 1     1 1 2 3    1/2  1/2  3/4  7/8
      1 0 1 0     1 1 2 2    1/2  1/2  3/4  3/4
      1 0 0 1     1 1 1 2    1/2  1/2  1/2  3/4
      1 0 0 0     1 1 1 1    1/2  1/2  1/2  1/2
      0 1 1 1     0 1 2 3     0   1/2  3/4  7/8
      0 1 1 0     0 1 2 2     0   1/2  3/4  3/4
      0 1 0 1     0 1 1 2     0   1/2  1/2  3/4
      0 1 0 0     0 1 1 1     0   1/2  1/2  1/2
      0 0 1 1     0 0 1 2     0    0   1/2  3/4
      0 0 1 0     0 0 1 1     0    0   1/2  1/2
      0 0 0 1     0 0 0 1     0    0    0   1/2
      0 0 0 0     0 0 0 0     0    0    0    0

At time 0, N parameters are true. At time 1, (1/2 + 3/4 + 7/8 + 15/16 = (8+12+14+15)/16 = 49/16) roughly 3 parameters are true. After that, the math gets complicated.

A way of approximating is to consider only the leftmost true parameter, that is, the parameter with the fewest true dependencies (only itself) and therefore the greatest chance of turning false. Once it turns false, it can't come back to true, so the role of leftmost parameter passes to the next parameter.

Since in a given turn, there's a 1/2 chance that the leftmost true parameter will fail, on average, it will take 2 turns for the leftmost parameter to fail. In the turn it fails, there's an additional 1/4 chance that the next leftmost also fails, and a 1/8 chance that the next leftmost also fails, and so on.

Therefore, the average expected "lifespan" of a given parameter is a little less than 2N, where N is the number of initially true parameters.

d) when Dependencies is true everywhere

Parameters[] decays to all false in roughly N2N turns.

Each true parameter depends upon all of the other parameters. Therefore, if in a given turn, M parameters are currently true, then the chance of a parameter being false next turn is roughly 1/M2.

A parameter goes false "for good" when all its dependees are false. The chance of all its dependees being false is (1/M2)M = 1/M2M

When a parameter goes false for good, not only it, but ALL of the co-dependent parameters go false for good (i.e., the entire set of parameters, since they are all co-dependent).

Therefore, the entire set will go false for good in roughly N2N turns. It's actually a little less than that, because each turn has a 1/M2M chance of complete failure, and M <= N.

e) when Dependencies is true in a block diagonal pattern

Parameters[] decays to all false in roughly 2(N/2)N turns.

Assume block size = 1, and that the pattern is aligned on the diagonal (i.e. in a 3x3 matrix, the following are true: [1,1], [1,3], [2,2], [3,1], [3,3]). This is the pattern my program uses.

Regardless of block size, the parameters form two subsets of co-dependent parameters. (The subsets themselves are independent). Therefore, if in a given turn, M parameters are currently true, then the chance of a true parameter being false next turn is roughly 1/(M/2)2.

The expected time to failure for a given subset is roughly (M/2)2*M/2 = (M/2)M turns, so we can expect both parameter subsets to have failed by (roughly) turn 2(N/2)N (actually a little earlier, for the same reason I mentioned in part d).

f) when Dependencies is determined randomly

I'd guess the average expected time to failure is half that of the case where all the Dependencies are true. So, I'll guess that Parameters[] decays to all false in roughly N2N/2 turns.

This is just a guess! I wonder how you'd calculate this mathematically...

I verified all of these by testing them. I didn't wait for cases d and e to go all the way through for large sizes.

4.2 Testing Time

Since size can go up to 24, there can be up to 24 * 24 = 28 = 256 elements in Dependencies[][]. Each element can be true or false, so there are 2256 possible settings for the Dependencies[][] array.

There are also 24 = 16 elements in Parameters[], any of which can be set to true or false. So there are 216 different initial settings for Parameters[].

In all, for size=24=16, there are (2256 * 216 = 2272) possible input settings. This is just for size=16. We must also consider sizes of 15, 14, etc. on down to size = 1.

In general, there are 2size(size + 1) input combinations. So, in all, there are SUM16i=12i(i+1) input combinations = 2272 + 2210 + ... + 22 = still only a little more than 2272.

2272 = (210)27.2 = roughly (103)27.2 = roughly 1082

  1. There are roughly 1082 different test cases.
  2. Each test takes 1 nanosecond, and 1 nanosecond = 10-9 seconds / (60 seconds/minute * 60 minutes/hour * 24 hours/day * 365.25 days/year * 109 years/AU) = 3.1688 * 10-26 AU
  3. The total testing time is therefore around 1082 * 3.1688 * 10-26 AU = 3.1688 * 1082-26 = around 1056 AU.

You can probably take short cuts by assigning equivalence classes.For instance, consider the cases where N = 2:

CLASS A      CLASS B      CLASS C
-------     ----------  ----------   etc.
  1 1       1 1   1 0    0 1   1 1
  1 1       0 1   1 1    1 1   1 0

However, for a thorough, brute-force black-box testing (which I think is the purest and most convincing form of testing), you wouldn't be allowed to take any shortcuts.

4.3 Extra Credit:

If size can go up to 216 = 65536, then there will be a little more than 265536*65537 = 24295032832 test cases. This is roughly (103)429503283.2 = 101288509850 test cases.

The total testing time is therefore around 101288509850 * 3.1688 * 10-26 AU = 3.1688 * 101288509850-26 = around 101288509824 AU.