Consider a domain of size n = 5000. A: Generate random numbers in the domain [n] until two have the same value. How many random trials did this take? We will use k to represent this value.

Question

Birthday Paradox Consider a domain of size n = 5000.

A: Generate random numbers in the domain [n] until two have the same value. How many random trials did this take? We will use k to represent this value.

Answer 1

Pseudocode:

Boolean isUnique[5001] = true;

int count = 1;

num = Random(5001) // Random between 0 and 5000

While (isUnique(num) == true)

isUnique(num) = false;

num = Random(5001) ;

count++ ;

end while;

Output ("Duplicate found in "+num+" tries.");

Answer 2

HERE IS THE CODE:

class BirthdayParadox

{

private int N=0;

boolean A[];

BirthdayParadox ( int n)

{

N=n;

A = new boolean[N];

for (int iLoop=0; iLoop<N; iLoop++)

{

A[iLoop]=false;

}

}

public int Go()

{

boolean done_flag = false;

int count=0;

while (done_flag==false)

{

int iIndex = (int) (Math.random()*(N-1))+1;

System.out.println(iIndex);

if (A[iIndex]==false)

{

count++;

A[iIndex]=true;

}

else

{

System.out.println(" Match found on " + iIndex);

done_flag = true;

break;

}

}

System.out.println(" count = " + count);

return(count);

}

public static void main(String args[])

{

BirthdayParadox myBirthdayParadox = new BirthdayParadox(5000);

myBirthdayParadox.Go();

}

} //class