Computer Science 1xx – Assignment #N

DUE DATE: mmddyyyy  

Functions and Random Numbers: Monte Carlo Integration

 

Learning Objectives:
(This is a list of the major topics that you, as students, will learn in this assignment:)

  1. Function Decomposition
    In this assignment, you will be given a problem, and then 'decompose' (break down) that problem into smaller parts, and solve each smaller part with one function/method/subroutine.  You may then decompose some of those smaller functions further.  The goal is to make your code easier to understand, to maintain, and to reuse.
     
  2. Algorithm Implementation
    In this assignment, you will be told how a certain goal must be accomplish (you have an algorithm described to you).  You must write a program that implements the described algorithm, in a way that is correct, and as time/space efficient as possible.  Time-efficient means that it runs as fast as it can (while still being correct) ; space-efficient means that it doesn't use excess/unneeded memory (while still being correct)
     
  3. Arrays
    In this assignment, you will need to manipulate an array of numbers, so that your code executes correctly.

Grading Rubric: This document is available for you use - you should use it to  to help guide your work.  The rubric is a document which explains how your work will be evaluated, and is located here.

Writing the program

Let's say that we want to find the area of a circle.  Let's further say that we don't remember the formula, aren't allowed to look it up, and can't remember how to derive the formula from other math that we know.  One approach to solving this problem is by using a 'brute force' approach – something kind of dumb, but that will work, if given enough computational power.  For this particular problem, we'll use the 'Monte Carlo Integration Method', which amounts to this:

1.      Draw the circle on a sheet of paper.  Remember how big the paper is (how high & how wide, which gives us the total area), and how big the circle is.

2.      Randomly pick points on the paper (say, by throwing darts).  For each point we randomly pick, we'll do the following:

a.       If the point is inside (or on the line of) the circle, we'll increment our counter that keeps track of the number of  points that landed inside the circle.

b.      If the point isn't inside/on the circle, and you need to, and increment another counter to keep track of that.

c.       Either way, increment your "How many times did I pick a point?" counter

d.      Darts that fall outside the paper are ignored entirely. 
Even better would be to find a way to make sure that your randomly selected points never end up outside the paper in the first place.

3.      Once you're done throwing all the darts in step 2, figure out what percentage of the darts fell inside the circle.
As an example, let's say you threw 1,000 darts, 534 of them landed inside/on the boundary of the circle, and 466 landed outside the circle, but on the paper.  Thus, 53.4% of the darts landed in the circle.

4.      Figure out how big the sheet of paper is (what the total area is).
As a continuing example, let's say that the paper is 100 inches wide, and 200 inches tall, for a total area of (100x200=20,000)

5.      Estimate that the area of the circle to be the size of the paper, multiplied by the percentage of points that were inside the circle.
As a continuing example, we'll estimate that the size of the circle is 53.4% of 20,000, or (20,000 * .534=) 10,680 square inches.

The downside is that this is computationally intensive (i.e., you can't really do this by hand). The upside is that this works for *ANY* shape, no matter how complicated.  For this homework assignment, we'll stick with circles, and only circles.

Your task is to write a program that will demonstrate how accurate this method is, depending on how many points you randomly select.  Basically, you're going to go through, and use the Monte Carlo method to estimate the area of the circle, then use the real formula to find the actual area, then compare the two.  The 'error' here will be measured as the percentage difference between the estimated & real circle (so if the circle is 314 units in size, and the estimate is 0, then the error is -100%, meaning that we're 100% below the real size.  If the estimate is 345.4 units, then the error is +10%, meaning that we're 10% over the actual size).

An example of the output is given below.   Everything that's highlighted in gray is optional output – your program isn't required to produce this output, if you don’t want to.  The rest of it is required output.  Make the columns of the table line up as best you can.

In addition to accomplishing the above objective, you have two additional, technical goals:

1.      Use functions and methods in order to modularize your code as much as possible.  If you know how to, and want to create classes here, that would be great.

2.      You want to minimize the amount of code you copy-and-paste, so use an array to store the number of points to randomly select each time, and iterate through that.  In the below example, there's an array that holds 1, 10, 100, 500, 1000, 5000, 10000, 50000, 100000.  The objective here is that by adding numbers to / removing numbers from this array, we can quickly & easily try different numbers of points.  The program should run correctly for different numbers of points, even if the only thing changed between runs are the numbers in that array.  Similarly, in order to make sure that you could test out many different sized circles (and on different sized sheets of paper), make sure to set up your code so that you can change the size of the paper by changing just one (or maybe two) variables (instead of simply writing in '100' everywhere for the size of the paper), and that you can change only a few variable(s) if you want to change the location or size(radius) of the circle.

Example Output

Welcome To The MonteCarlo Circle Area Estimator!!

 

Max X: 100

Max Y: 100

Total Area of Surrounding Space: 10000

Basing our estimate on 1 randomly selected points

% of Randomly Picked Points Inside The Circle: 0

Estimated Total Area Of the Circle: 0

Actual Total Area Of the Circle: 314.159265358979

The estimate was off by 314.159265358979, which is -100% of the real circle

************************************************************

Max X: 100

Max Y: 100

Total Area of Surrounding Space: 10000

Basing our estimate on 10 randomly selected points

% of Randomly Picked Points Inside The Circle: 0

Estimated Total Area Of the Circle: 0

Actual Total Area Of the Circle: 314.159265358979

The estimate was off by 314.159265358979, which is -100% of the real circle

************************************************************

Max X: 100

Max Y: 100

Total Area of Surrounding Space: 10000

Basing our estimate on 100 randomly selected points

% of Randomly Picked Points Inside The Circle: 0

Estimated Total Area Of the Circle: 0

Actual Total Area Of the Circle: 314.159265358979

The estimate was off by 314.159265358979, which is -100% of the real circle

************************************************************

Max X: 100

Max Y: 100

Total Area of Surrounding Space: 10000

Basing our estimate on 500 randomly selected points

% of Randomly Picked Points Inside The Circle: 0.026

Estimated Total Area Of the Circle: 260

Actual Total Area Of the Circle: 314.159265358979

The estimate was off by 54.1592653589793, which is -17.2394295922144% of the rea

l circle

************************************************************

Max X: 100

Max Y: 100

Total Area of Surrounding Space: 10000

Basing our estimate on 1000 randomly selected points

% of Randomly Picked Points Inside The Circle: 0.024

Estimated Total Area Of the Circle: 240

Actual Total Area Of the Circle: 314.159265358979

The estimate was off by 74.1592653589793, which is -23.6056273158902% of the rea

l circle

************************************************************

Max X: 100

Max Y: 100

Total Area of Surrounding Space: 10000

Basing our estimate on 5000 randomly selected points

% of Randomly Picked Points Inside The Circle: 0.0262

Estimated Total Area Of the Circle: 262

Actual Total Area Of the Circle: 314.159265358979

The estimate was off by 52.1592653589793, which is -16.6028098198468% of the rea

l circle

************************************************************

Max X: 100

Max Y: 100

Total Area of Surrounding Space: 10000

Basing our estimate on 10000 randomly selected points

% of Randomly Picked Points Inside The Circle: 0.0301

Estimated Total Area Of the Circle: 301

Actual Total Area Of the Circle: 314.159265358979

The estimate was off by 13.1592653589793, which is -4.18872425867901% of the rea

l circle

************************************************************

Max X: 100

Max Y: 100

Total Area of Surrounding Space: 10000

Basing our estimate on 50000 randomly selected points

% of Randomly Picked Points Inside The Circle: 0.03042

Estimated Total Area Of the Circle: 304.2

Actual Total Area Of the Circle: 314.159265358979

The estimate was off by 9.95926535897934, which is -3.17013262289088% of the rea

l circle

************************************************************

Max X: 100

Max Y: 100

Total Area of Surrounding Space: 10000

Basing our estimate on 100000 randomly selected points

% of Randomly Picked Points Inside The Circle: 0.03225

Estimated Total Area Of the Circle: 322.5

Actual Total Area Of the Circle: 314.159265358979

The estimate was off by 8.34073464102067, which is 2.65493829427249% of the real

 circle

************************************************************

Max X:            100

Max Y:            100

Radius of Circle: 10

Num Points      Off by (%)

1               -100%

10              -100%

100             -100%

500             -17.2394295922144%

1000            -23.6056273158902%

5000            -16.6028098198468%

10000           -4.18872425867901%

50000           -3.17013262289088%

100000          2.65493829427249%

 

 

Group Work, Commenting:

 

            You are not allowed to work in groups for this assignment.  You should start, finish, and do all the work on your own.  If you have questions, please contact the instructor.

 

            Additionally, you should aggressively comment your code, paying particular attention to areas that are difficult to understand.  If you found something to be tricky when you wrote it, make sure to comment it so that the next person (the instructor, who's grading you) understands what your code is doing.  It is not necessary to comment every single line.

 

The purpose of new requirement is to both help you understand, and have you demonstrate, a thorough understanding of exactly how your program works.

 

Every file that you turn in should have:

·        At the top of each file that you normally edit, you should put your name (first and last), the name of this class (“BIT 142”), and the year and quarter, and the assignment number, including the revision number, which starts at 0 (“A2.0”).  If you’re handing this in again for a regrade, make sure to increase the minor version number by one (from “A2.0”, to “A2.1").
You normally edit the C# source code files (.CS files), and any Word documents that you're handing in (if any).
You do not normally edit the .SLN or .CSPROJ files, and so you should not try to put this identifying information in those files.

 

In general, you should make sure to do the following before handing in your project:

·        All variables used should have meaningful names.

·        The code should be formatted consistently, and in an easy to read format.   

 

What to turn in:

 

·        A single electronic folder (a directory).  This folder should contain:

o       The source code for the program – all the .CS files in your project.
I would prefer that you include the project files – stuff ending in .SLN and .VCPROJ, so I can build your project more easily.  If you can save these files (the .SLN / . VCPROJ) into a file format that can be opened by VS.Net 2003, that would be great.

o       You have to name the folder with your last name, then first name, then the assignment number (both the major version – 2, and the minor (revision) number – 0).  Example: "Panitz, Mike, A2.0"

 

·        You should not include the Debug directory, or anything from it.  I will dock you a couple points if you do.  Also, you don't need to include your .NCB file, if it's present.

 

How to electronically submit your homework:

 

There's a link on the homework page to the document that guides you through handing in your work, using the SourceGear Vault program.

 

 


This document and the related materials are developed with support from Microsoft Research Computer Gaming Initiative under the Computer Gaming Curriculum in Computer Science RFP, Award Number 15871.