Practice for PE (CS1101 AY2007/8 Semester 1)

Date of release: 16 October 2007, Tuesday 23:59.

Submission deadline: 24 October 2007, Wednesday 23:59.

School of Computing, National University of Singapore

This is an **ungraded** assignment.

This assignment is given out as a practice for your Practical Exam (PE). In the PE, you will be given 2 or 3 problems, with the first one usually being the easiest. The exercise in this assignment resembles an easy problem. You should try this exercise in a simulated test environment, by timing yourself.

The time taken to complete this exercise, including reading, designing,
coding and testing, should be **no more than 45 minutes**.

In your PE, you may be given a very small number of submissions, hence it is even more important for you to test your program thoroughly before you submit it.

To simulate the PE environment (just in case you will be given a very
small number of submissions), the number of submissions for this
assignment is set to **3**.

*This problem is adopted from last year's National Software Competition
for junior college students. (Copyright: NSC 2006.)*

Professor Robert A.J. Matthews of the Applied Mathematics and Computer Science Department at the University of Aston in Birmingham, England, has recently described how the positions of stars across the night sky may be used to deduce a surprisingly accurate value of p. This result followed from the application of certain theorems in number theory.

Here, we don't have the night sky, but we can use the same theoretical basis to form an estimate for p.

Given any pair of positive integers chosen from a large set of
random numbers, the probability that the two integers have no
common factor other than one is
**6/p ^{2}**.

For example, using this small set of five numbers: {2, 3, 4, 5, 6}, there are 10 pairs that can be formed: (2,3), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6), (4,5), (4,6) and (5,6). Six of these 10 pairs: (2,3), (2,5), (3,4), (3,5), (4,5), and (5,6) have no common factor other than one. Using the ratio of the counts as the probability we have:

6/p^{2} = 6/10. Hence the estimated value of
p is 3.1623, correct to four decimal
places.

As another example, given this set of 10 numbers {32391, 14604, 3902, 153, 292, 12382, 17421, 18716, 19718, 19895}, there are 24 pairs that have no common factor other than one, among a total of 45 pairs. We have:

6/p^{2} = 24/45.
Hence the estimated value of p
is 3.3541, correct to four decimal places.

Write a program `EstimatePI.java` that reads in a positive
integer *n* representing the size of the list, followed by
*n* lines of unique positive integers. This program uses
the `IntegerList` class which is defined in the
`IntegerList.java`, to create an `IntegerList`
object, and then prints out an estimate value for
p accurate to 4 decimal places.

The set contains at most 50 unique integers.

You are given these partial codes:

- IntegerList.java (incomplete code)
- EstimatePI.java (incomplete code)

Sample run using interactive input (user's input shown in
blue; output shown in
**bold purple**):

$ javac EstimatePI.java $ java EstimatePI 3 7 4 103.0000

Sample run #2:

$ java EstimatePI 5 2 3 4 5 63.1623

Sample run #3:

$ java EstimatePI 10 32391 14604 3902 153 292 12382 17421 18716 19718 198953.3541

Submit your programs `IntegerList.java` and
`EstimatePI.java` through CourseMarker.

- This lab assignment is labelled as
**labPT3**on CourseMarker. - As a preparation for your PE, try to spend
**no more than 45 minutes**(including reading, designing, coding and testing) on this exercise.

The deadline for handing in all programs is **24 October 2007, Wednesday
23:59**. Late submissions will NOT be accepted.

tantc@comp.nus.edu.sg

Mon Sep 24 13:52:22 SGT 2007