Arrays - A Concise and Practical Introduction to Programming Algorithms in Java - page 103

- First, the smallest prime integer is 2. Strike off 2 and all multiples of
2 in the array (setting the array elements to false ),

- Retrieve the smallest remaining prime number p in the array (marked
with boolean true ), and strike off all multiples of p ,
- Repeat the former step until we reach at some stage p> √ N , and list
all prime integers.

Design a function static int[] Eratosthene(int N) that returns in
an integer array all prime numbers falling in range [2 ,N ].
Exercise 4.7 (Image histogram)

Consider that an image with grey level ranging in [0 , 255] has been
created and stored in the regular bi-dimensional data-structure byte
[] [] img; . How do we retrieve the image dimensions (width and
height) from this array? Give a procedure that calculates the histogram
distribution of the image. ( Hint: Do not forget to perform the histogram
normalization so that the cumulative distribution of grey colors sums up
to 1.)
Exercise 4.8 (Ragged array for symmetric matrices)

A d -dimensional symmetric matrix M is such that M i,j = M j,i for all
1 d . That is, matrix M equals its transpose matrix: M T

≤ i, j ≤ = M .

Consider storing only the elements M i,j with d 1intoa ragged

array: double [] [] symMatrix=new double [d][]; . Write the array
allocation instructions that create a 1D array of length i for each row of
the symMatrix . Provides a static function that allows one to multiply two
such symmetric matrices stored in “triangular” bi-dimensional ragged
arrays.
Exercise 4.9 (Birthday paradox **)

≥ i ≥ j ≥

In probability theory, the birthday paradox is a mathematically well-
explained phenomenon that states that the probability of having at least
two people in a group of n people having the same birthday is above

1
2

for n 23. For n = 57 the probability goes above 99%. Using the

Math.random() function and a boolean array for modeling the 365 days,
simulate the birthday paradox experiment of having at least two people
having the same birthday among a set of n people. Run this birthday
experiment many times to get empirical probabilities for various values
of n . Then show mathematically that the probability of having at least
two person's birthdays falling the same day among a group of n people
is exactly 1

≥

365!
365 n (365 −n )! .

−