Question

Write a program that takes an integer N from the command line and uses StdRandom.uniform() to generate a random sequence of integers be- tween 0 and N – 1. Run experiments to validate the hypothesis that the number of integers generated before the first repeated value is found is ~√?N/2.

Answer 1

// Please refer to the screenshot of the code to understand indentation.

// Feel free to ask any doubts by commenting on the answer

// You will need 2 additional files because of the requirement to use StdRandom.uniform() function (StdRandom.java and StdOut.java). Download those files from Princeton University's database and keep them in the same folder in which you keep the following code.

// I've generated a sequence till an integer is repeated. This generation was repeated for 1000 times so that an average result value could be obtained to compare it to the hypothesised value.

public class Main
{
   public static void main(String[] args) {
   // N = Value of N from command line
   int N =   Integer.parseInt(args[0]);
   // numRepeats = Number of times sequence is generated
   int numRepeats = 1000;
   // numInts = Average number of integers to be generated before the first repeated value is found
   int numInts = 0;
   // hypothesis = Hypothesised number of integers root of (2*pi/n)
   double hypothesis = Math.sqrt(Math.PI * N / 2);
   // Generate a sequence until a repeated value is found for numRepeats(=1000) times
   for (int i=0; i<numRepeats; i++)
   {
   // Value at index i of arr is 1 if the integer i has been generated previously
   int[] arr = new int[N];
   // x = Integer generated by function uniform
   int x = StdRandom.uniform(N);
   // counter = Number of integers generated before a repeated integer is found in the current sequence
   int counter = 1;
   // Repeatedly generate integers until the first repeated integer is found
   while (arr[x] != 1)
   {
   // Flick the value at x index of arr to 1
   arr[x] = 1;
   // Generate a new integer and store it in x
   x = StdRandom.uniform(N);
   // Increase the variable counter by 1
   counter++;
   }
   // Accumulate counter to numInts
   numInts += counter;
   }
   // Divide numInts by numRepeats to obtain the average numInts
   numInts = numInts/numRepeats;
  
   // Print the final information
   System.out.println("N: " + N);
   System.out.println("On repeating the sequence 1000 times, a repeated value was found after "
   + numInts + " integers on average.");
   System.out.println("Hypothesised number of integers: " + hypothesis);
   }
}