Write a program SIM (meeting the usual requirements) that implements the Monte Carlo simulation for Stochastic Area Networks in section 2.4.4 of the text.

Input & Output

Your SIM program will take several arguments:

Your program should produce output such as (compared to the book's table on page 83, we are simply displaying the $\pi_k$ and $\hat{p}_a(\pi_k)$ columns):

OUTPUT    :a1/2,a2/3,a3/4,a4/6:    5.72632e-01
OUTPUT    :a1/3,a3/6:              1.81732e-02
OUTPUT    :a1/2,a2/5,a5/6:         1.51699e-03
OUTPUT    :a1/2,a2/3,a3/6:         9.45027e-02
OUTPUT    :a1/4,a4/6:              1.94422e-01
OUTPUT    :a1/3,a3/4,a4/6:         1.18930e-01

Note that the there is no specific order to the output,¹ but you must provide an entry for all possible paths. The paths should be formatted without any intervening white space, beware:

OUTPUT    :a1/2, a2/3, a3/4, a4/6:  5.72632e-01

is no good

The value provided for each path is the critical path point estimate described in the book. Use at least 6 significant digits and scientific notation for the point estimates. The output above is nicely formatted into columns, but your results don't need to be (in fact I've prettied up the aforementioned output from my own results).

SAN Description Files

1 2 3
2 3 5
1 4 6
1 3 2
4 3 1.5
4 5 6
3 5 4

Submit Your Work

grader.sh

Students have access to the same script I'm providing the grader for testing your SIM. Here is how to use it:

First, download this tarball to your Mines Linux account ("alamode" machines!) and unroll it in a temporary directory.

$ ls criticalpath-student.*
criticalpath-student.tar.bz2
$ mkdir tmp
$ cd tmp
$ tar xjf ../criticalpath-student.tar.bz2

Second, set the SIMGRADING environmental variable with:

$ source ~khellman/SIMGRADING/setup.sh ~khellman/SIMGRADING

Now go to the directory holding your CriticalPath SIM (is it ~/sim/critpath or something else?) and execute the grader.sh script from the criticalpath-student.tar.bz2 resource.

$ cd ~/sim/critpath
$ ls SIM
SIM
$ ~/tmp/CriticalPath/grader.sh
:
:
:

You will need to read any messages from the script carefully, and you may need to hit ENTER several times throughout its course. This script checks for:

1. missing tracefiles
2. truncated tracefiles
3. incorrect edge weight randomization
4. correct reporting of multiple critical paths
5. a result formatting

6. and the difference between SIM results and expected results

The latter test generates PDFs files for your inspection. The red dots are the result of SIM point estimates using $N=1000$ replications; the blue dots are the expected results from eight $N=300$ trials. The $x$ coordinate for all plots are the point estimates from an $N=10000$ experiment. The grey line is the line of identity ($y=x$). Your SIM's red dots should be closer to the line of identity than most of the blue dots.

Here is an example of one of the plots generated by grader.sh:

Rubric

This work is worth 46 points.