CIS461-DL     Dr. J. Scher        HomeMiniExam #2    Due: Thursday, February 5, 4:00 PM

Home Mini Exam #2: Using Simulation to Solve a Simple Stochastic Geometric Problem

Viewing: We assume that you have already carefully viewed Videotapes 1, 2, 3 and 4. Videotape 2 provided you with some basic definitions and terminology used in systems simulation. In videotape 3, I take you very slowly through the analysis and design phase of a simulation approach to solving a simple geometric problem, namely, determining the probability that two random cuts in a stick produce three substicks which can form a triangle. In videotape 4, we study a popular algorithm for generating pseudorandom numbers.  (The associated textbook reading for each of the Videotapes is enumerated in the CIS461 Course Syllabus)

The Geometric System to be Simulated

1. Suppose, as in the videotape lecture, that two random cuts are made in a stick, resulting in 3 substicks. Let substick S be the smallest of the 3 substicks. Suppose a random cut is made in substick S, resulting in two additional substicks, S1 and S2. 
2. Take the smaller of the substicks S1 and S2, and toss it aside, so we are left with the two original substicks and the larger of substicks S1 and S2. 

 Simulate the above process for  100,000  sticks, and have your simulation study determine the probability that the resulting 3 substicks can be rotated to form a triangle. 

(Intuitively, do you feel that this process should result in a higher probability of a triangle being formed than the process simulated in the videotape?)

Using the simulation approach outlined in videotape 3, you are to write a simulation program in the language (HLL) of your choice (C, C++, Pascal, Fortran, etc.) to simulate the above system for 100,000 sticks, and determine and output the desired probability. You may use the built-in random number generator procedure in the language of your choice (you will need to consult your programming language documentation to access this procedure).

Your internal documentation for the software you create must consist of the following:
1) Your name
2) A Variable Glossary. 
3) The Source Code Listing in the HLL of your choice (with moderate included in-line documentation to improve readability), and the output (i.e., the simulated estimate of the probability).

Your external documentation should have the presentation and discussion of your output. (A flow diagram or pseudocode is highly recommended, but will not be graded.)

ASIDE: Do NOT procrastinate! This assignment will require some significant design and implementation time. (If there is any student who has not programmed in a while in a HLL, and feels he/she is unable to do this Home Mini Exam on their own, please email Dr. Scher on or before Monday, February 2, explaining the circumstances and a chosen partner in the class, and Dr. Scher will allow you to "team up" with another student of your choice in our class, with a single submission, and a single grade will be awarded, provided that each student contributes equally to the submission. This liberalization of the non-collaboration rule is being offered primarily as a service to non-CCS majors who might need a little "helping hand" to get back into programming, after an absence from doing any programming.)