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/p2.
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/p2 = 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/p2 = 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:
Sample run using interactive input (user's input shown in blue; output shown in bold purple):
$ javac EstimatePI.java $ java EstimatePI 3 7 4 10 3.0000
Sample run #2:
$ java EstimatePI 5 2 3 4 5 6 3.1623
Sample run #3:
$ java EstimatePI 10 32391 14604 3902 153 292 12382 17421 18716 19718 19895 3.3541
Submit your programs IntegerList.java and EstimatePI.java through CourseMarker.
The deadline for handing in all programs is 24 October 2007, Wednesday 23:59. Late submissions will NOT be accepted.