Brock University

Department of Computer Science

Fall
2017 Instructor:** Vlad Wojcik****
**

Assignment # 1: Due : Wednesday, 18 Oct 2017, 4 PM.

PROBLEM 1: Approximations of Pi[30 marks]A circle of diameter 1 is positioned so on the Oxy plane that its center has coordinates (0.5, 0.5). Let us consider the square circumscribing that circle, with one corner placed at (0, 0). The sides of this square have length 1 and are oriented either horizontally or vertically, of course.

Suppose that the square and the circle it contains are our target, which we aim to hit with a rifle. Suppose further that we are particularly bad shots. In fact, we can always hit the square, but we are so clumsy that any spot in the square has equal chances of being hit. Do you see that if we executed M shots, and counted the number N of shots that also hit the circle, then the expression

4.0 * (float)N / (float)M

approximates the number Pi? In fact, this algorithm may be used to calculate the value of Pi with arbitrary accuracy, for sufficiently large M.

Suppose further that X and Y are independent random variables of uniform distribution in an interval [0, 1]. Then the pair (X, Y) can be considered a single "shot" of the square. In practice, the values X and Y are obtained by using a suitable random number generator.

Write a program that would tabulate a series of approximations of Pi every 1000 shots up to 32000 shots (in a multi-column format, to save paper).

Below is a Pascal code for a suitable, industrial strength, random number generator returning uniformly distributed float numbers in the interval [0, 1]. Study that code and translate it into a suitable function in C++ or Ada.

PROGRAM Random(Output);CONST seed1 = 5; seed2 = 10000; seed3 = 3000;VAR x, y, z : integer; loop : integer;FUNCTION Unif : real; Var tmp : real; Begin {Unif} x := 171*(x mod 177) - 2*(x div 177); if x<0 then x := x + 30269; y := 172*(y mod 176) -35*(y div 176); if y<0 then y := y + 30307; z := 170*(z mod 178) -63*(z div 178); if z<0 then z := z + 30323; tmp := x/30269.0 + y/30307.0 + z/30323.0; Unif := tmp - trunc(tmp) End; {Unif}BEGIN x := seed1; y := seed2; z := seed3; for loop := 1 to 1000 do writeln(loop:4, ' ==> ', unif:7:5) ENDNOTES on Pascal: The following points may be of help:

Assignment operator in Pascal is :=

Curly braces contain comments

BEGIN in Pascal translates to { in C++

END in Pascal translates to } in C++

Pascal's type real is known as float (or double) in C++

div stands for integer division

mod stands for the remainder of integer division

The function trunc truncates the fractional part of the real number

Although the use of global variables is normally bad programming practice, generation of random numbers is a notable exception. Observe that the changes to the variables x, y, z made in one call to the function Unif must be available in the next call to Unif. In other words, the variables x, y, z must be global to Unif.

PROBLEM 2:Pairing Primes[30 marks]A prime number is a positive integer divisible only by 1 and itself. For example: the numbers 2, 3, 5, 7, ... are prime. There are infinitely many prime numbers, of course. This can easily be proven.

Proof that there are infinitely many prime numbersis usually done by contradiction. Suppose that all prime numbers would form a finite sequence of some length n like this:P1, P2, P3, ... , Pn

Let us create a new number X = 1 + P1 * P2 * P3 * ... * Pn. This number is not divisible by any prime number from the sequence P1, P2, P3, ... , Pn, hence it must be prime. But X is not the member of the sequence P1, P2, P3, ... , Pn. From this we deduce that the sequence of all prime numbers cannot be finite.

Q.E.D.Prime numbers have many amazing properties. One of them is that they come in pairs (x, y) where y - x = 2. Examples of such pairs: (3, 5), (5, 7), (11, 13), (17, 19), ... But: Is the sequence of such pairs finite or infinite? Nobody knows.

Let us investigate prime numbers a bit further. Write a program that would

- Print out all prime numbers less than 30000 (in as many numbers per row as possible, to save paper), and
- Print out all pairs from among these numbers, one pair per row, in a milti-column format (to save paper):

Pair xx: (x, y) where xx is the pair number.

HINT: How can we identify all primes smaller than 30000? We might use a method known from antiquity as Sieve of Erathostenes. The computerized version of this method would look more or less like this:Let us declare an Boolean array of 30000 elements, all initialized to FALSE. We will use the index of this array to identify our prime numbers. Our algorithm would look as follows:

- Set the index to 2 because we know that 2 is the first prime number. Print out that prime number.
- Assign value TRUE to all array elements identified by the multiples of that index, i.e. to elements number 4, 6, 8, ... , 30000
- Keep incrementing the index by one until you find an array element holding value FALSE. The value of that index is a prime number. Print out that prime number.
- Assign value TRUE to all array elements identified by the multiples of that index, as before.
- Go to step (3) while making sure that your index value always remains valid, i.e. is less than 30000.

PROBLEM 3: Simulation of Life[30 marks]Life is a complex thing, but it appears that it is only a superposition of many simple rules. Let us simulate life by following an idea of John Conway (at left), professor of Finite Mathematics of Princeton University. This idea of his is known as the "Game of Life".

Consider an artificial Petri dish: an array of 20 x 20 cells. Each of the cells in the interior of the array has exactly eight neighbours: two horizontal neighbours, two vertical neighbours, and four diagonal neighbours. The cells on the border of the dish have fewer neighbours: for example the corner cells have only three neighbours each.

We can make sure that all cells in our dish have exactly eight neigbours, by deforming our dish. If we bend our dish horizontally so that the edges touch, the cells of the first and the last column will become neighbours, while our dish will become a cylinder.

If we then bend our cylinder so that its ends meet, the cells in the first and the last row will become neighbours, and the cylinder will become a torus (a fancy word used by mathematicians to describe an inner tube).

Every cell on a torus has exactly eight neigbours. The progress of life is simulated by a sequence of snapshots of our toroidal Petri dish, each snapshot representing a generation. The rules of life are as follows:

- A cell may be "alive" or "dead".
Birth rule: If a dead cell has exactly three alive neigbours, it will become alive in the next generation.Survival rule: An alive cell with two or three alive neigbours will survive to the next generation.Default rule: In all other cases the cell dies or remains dead (this simulates death by "loneliness" or "overcrowding").Please note that the number of live neighbors is always based on the cells before the rule was applied. In other words, we must first find all of the cells that change before changing any of them.

Write a C++ or Ada program that would display on the screen up to 20 generations of life in our Petri dish, as long as there is "life" in our dish. The alive cells should be displayed as 'X', the dead cells should be shown as spaces.

The dish should be initialized by a random number generator, reused from Program 1 above. Your program should prompt the user for three seed values for the generator. This would allow you to generate different random number sequences in order to obtain different dish initialization patterns. Let us observe the convention that a cell is initialized to be "dead" if the number obtained from the generator is less than 0.6, and is "alive" otherwise.

You may find it interesting to observe that certain "organisms" in the dish go extinct, others "evolve", still others go on "living" forever. By an "organism" we mean a collection of live cells of a particular shape. Of course, you could change the threshold value 0.6 to some other value controlling our random number generator that "breathes life" into our Petri dish.

PREPARATION FOR ASSIGNMENT SUBMISSION:For convenience, students may code and compile their program assignments using a variety of platforms and compilers that are not available in the Computer Science Labs. During assignment marking, if assignments have been submitted in any of these miscellaneous formats, the marker will not be able to compile and test run the assignment in the Lab and therefore, will not be able to provide a mark. It is the responsibility of each student to compile and test run their assignment program on the software provided either in Labs D205 or J310. The following software is available in the lab: Visual Studio 2015, AdaCore GPS 2016, Redhat Linux 6 or Unix on Sandcastle.

Checklist of items before submission:

- Include a brief one page outline of program design.
- Compile and test run assignment program in Lab.
- Make sure all files are included in the submission folder.
- Include any special instructions for compiling and running if using Unix platform.
- Include a copy of assignment program output for markers use.

SUBMISSION FORMAT:

Both hardcopy (paper) and electronic submission is required.

Hardcopy submission:Your submission envelope with the standard Cover Page should contain all relevant printouts and supporting documentation, demonstrating your design and flawless behaviour of your program. The envelope should be dropped in the submission box on or before deadline date / time.

Electronic submission:Please create a directory on Sandcastle and place within it all the files (and only the files) to be submitted. To submit issue the command, which is interactive in its nature. Obviously, you are allowed to submit your assignment only once. Should you encounter difficulties, please report them to your TA.submit4f00Similarly, the electronic submission should be performed on or before deadline date / time.

PENALTIES:Possible lateness in assignment submission is counted in days, each period of a day ending at 4 PM. The penalty for late submission of assignments is 25% up to three days (or a part of a day). After that period the penalty is 100%.

While honest cooperation between students is considered appropriate, the Department considers

plagiarisma serious offense. For clarification on these issues you are directed to the statement ofDepartmental Policies and Procedures.

Instructor: Vlad Wojcik

Revised: 20 September, 2017 1:03 AM

Copyright © 2017 Vlad WOJCIK