Description
Problem Description
Let A[1..n] be an array of n numbers. If i duplication of A.
Suppose that the elements of A are filled in by a uniform random number generator that
produces numbers in the range [1..n] (i.e., 1 ≤ A[i] ≤ n for i =1 to n).
In this homework, you are asked to compute expected number of duplications for an array of
size n with paper and pencil and then verify your calculation by a C++ program implementation,
as follows:
(a) Use indicator random variables to compute the expected number of duplications for an
array of n random numbers, as described above.
(b) Write a C++ program that
a. takes number of array elements (n) from the command line.
b. fills in the array with random numbers from the range [1..n].
c. outputs array elements (for clarity, output up to 10 array elements per line).
d. outputs expected number of duplications, based on your analysis in Part (a).
e. finds all the duplications of the array and prints them out.
f. outputs encountered number of duplications, based on the program run.
Two example program runs are given below:
Figure 1: An Example Program run with array size n = 30
Figure 2: An Example Program run with array size n = 100
Report
Your report must consist of two parts:
(1) In the first part, you must present your analysis for Part (a) above, i.e., use of indicator
random variables to compute the expected number of duplications.
(2) In the second part, analyze your program that is implemented in Part (b) and calculate
the running time of the algorithm.
Submission
Submit your homework files through Ninova. Please zip and upload all your files. You are
going to submit the following files:
(a) All your .h (if any) and .cpp files
(b) A .pdf file as your report. Your report should be clear and detailed. If your solutions
are unclear, it may result in a grade loss for you.
(c) A .txt file explaining how to compile and run your code (in a 1 or 2 line)
Use your student ID as file names. That is, your_student_id.zip for the .zip file,
your_student_id.cpp for the main C++ source file and your_student_id.pdf for the report.
