JAVA O This is a programming assignment to conduct experimentation on hash tables. The program must be written in Oracle Standard Edition compliant Java Part 1 Implement the following linear congruential pseudo-random number generator:

x_n+1 = (ax_n) mod M

where a = 7⁵ = 16807 and M = 2³¹ 1 = 2147483647. The seed value x₀ is determined appropriately. Write a function "pseudoRandom()" that returns x_n+1 from x_n. Use 64-bit integer type for the variables and constants (long type in Java, long long type in C++). Despite its simplicity, it is known to generate good pseudo-random numbers for many purposes, including this assignment. The program will have to compute the mean (average) as well as the standard deviation of data values. Let x₁, , x_n be data values. The mean (average) of the x_i is = (_1inx_i)/n. The standard deviation is s = [(_1in(x_i)²)/(n1)]^1/2. The standard deviation is a fundamental statistical quantity that measures the degree of dispersion of data values. The larger the standard deviation is, the more dispersed the data values are. A basic law of standard deviation tells us that there should be a large concentration of values in the range [s, +s]. In the following, m is the array size, n is the # of key values inserted into the table, and f(k, m) = m(fractional part of kA) = m(kA mod 1), A = (5 1)/2 0.6180339887498949. Write a program that performs the following experiments and displays the required statistical data legibly on the screen. Use 64-bit double type for floating-point numbers. Part 2 This part is experimentation on chaining method. Set the array size m to 1000003, which is a prime number.

1. Using the above random number generator, generate n integer key values starting from the seed value x₀ = 98760053, and insert them into the hash table using the hash function:

   h(k) = k mod m, where k is the generated key value

   Then compute and display the following data:
   • distribution of bucket sizes in terms of bucket size, # of buckets of this size, (# of buckets of this size)/(total # of buckets), listed in increasing order of bucket size
   • load factor = n/m
   • standard deviation of bucket sizes from load factor (load factor is the mean value in this case)
   Repeat this experiment for n = 800000, 1000000, 2000000, 3000000, each of the four starting from the same seed value 98760053. sample output for n = 2000000
2. Repeat the experiments in part (a) using the hash function:

   h(k) = f(k, m)

   sample output for n = 2000000