CSC $323$ Algorithm Design and Analysis, Fall $2024$

Instructor: Dr$.$ Natarajan Meghanathan

Assignment $1$: Analysis of the Element Uniqueness Problem

Due by: Sept. $19$th$,11\mathrm{.}59$ PM

In this programming assignment, you will implement the brute force algorithm discussed in Module $1$ for the

"Element Uniqueness Problem." Each of you have been assigned two $\text{'}$n$\text{'}$ values that correspond to the size of the

array. The two $\text{'}$n$\text{'}$ values are independent and must be considered separately.

For a particular $\text{'}$n$\text{'}$ value, the maximum value $($m$)$ for any element in the array would be: maxValueFactor $*$ n$,$ where

maxValueFactor $($an integer$)$ ranges from $1,2,3,...,10.$ For example, if n $=100,$ the maximum value $($m$)$ for any

element in the array could be: $100,200,300,400,500,600,700,800,900,1000.$

You are given a startup code that should be run for a particular array size $($n$)$ input by the user and it runs $1000$

iterations $($maxIterations $=1000)$ for a particular value of the maxValueFactor $($corresponding to a particular value

of m$),$ generating $1000$ different arrays and determining whether each of them is unique or not $($through a function

findUniqueness to be implemented by you$).$ The code in the main function takes care of adding the number of

comparisons encountered for all the $1000$ arrays in the form of a variable called totalComp. After running the

maxIterations, the code will print the values of maxValueFactor and average number of comparisons per array size.

Tasks:

$(1)$ Implement the function findUniqueness for a given array and array size, and return the number of comparisons

encountered to check for uniqueness for the particular array.

$(2)$ For the two array size values assigned to you, plot the maxValueFactor vs$.$ average number of comparisons per

array size in a single plot. Interpret your observations, including answers to the following questions:

$($a$)$ For a given array size, does the average number of comparisons increase with the maximum value for

any element in the array?

$($b$)$ For a given m $($i$.$e$.,$ maximum value for any element in the array$),$ does the average number of

comparisons increase with array size?

Note:

$(1)$ You should use the startup code provided. Otherwise, you will get a ZERO for the assignment.

$(2)$ If the instructor finds out that the student has used ChaptGPT for generating the code, the student will get a

ZERO for the assignment.

$(3)$ The code to test for element uniqueness should be inside the function findUniqueness and not in the main

function. If your code includes any user$-$defined functions or makes use of any built$-$in functions, you will get a

ZERO for the assignment.

$(4)$ The instructor could interview the student to explain any part of the assignment. If the student is not able to

convincingly explain what has been submitted, the instructor may give a ZERO for the assignment