Problems Description: Your algorithm first takes an input size $(10$ N from

the user. First, your program will generate a random sequence of N integers ranging

from $-999,999,999$ to $999,999,999$ and store them in an array A $($list in Python$).$ If N is

less than $50,$ your program must use random numbers ranging from $-99$ to $99$ and

print all randomly generated numbers on the screen. After generating random numbers,

your program takes an input K from the user again, and determines if there are two

numbers whose sum equals a given number K$.$ For instance, if the random numbers are $8,$

$4,1,6$ & $3$ and K is $10,$ then the answer is $$yes$($since $4+6=$ K$).$

Do the following:

Part I: Max $10$ points

$$ Give O$($N$2)$ algorithm to solve this problem. Analyze the complexity of your

approach using your Python code.

$$ Give O$($N log N$)$ algorithm to solve the problem $($Hint: Sort the array first using a

Python sort and search $).$ Analyze the complexity of your approach using your

Python code.

$$ Give O$($N$)$ algorithm to solve the problem $($Hint: Use the given implementation of

hash table. Assume the initial size of the hash table is $5,003).$ Describe your idea

and analyze the complexity of your approach using your Python code.

$$ Compute the running times of three algorithms above.

$($Write your code in Python for $($a$),($b$)$ and $($c$))$

Evaluate and compare the worst$-$case execution times of your algorithms for

identifying pairs with sums equal to KKK over a minimum of $10$ iterations. Then,

generate a plot showing the average worst$-$case execution times for input sizes of

$100,200,400,800,$ and $1600.($You may adjust the input size range based on your

computer's processing speed as needed.$)$

Make sure that you measured the worst$-$case execution time. An easy way to

measure the worst$-$case execution time is to make k greater than $2,000,000,000.$

$$ Plot the averaged worst$-$case execution times of your O$($N$2)$ and O$($N log N$)$ algorithms

for the selected input sizes in the first graph.

$$ Plot the averaged worst$-$case execution times of your O$($N log N$)$ and O$($N$)$ algorithms

for the selected input sizes in the second graph.

$($Your graphs must show the averaged worst$-$case executions time on the vertical axis and

the input sizes on the horizontal axis$)$

Part II $($optional$,$ up to $2$ extra points$)$: Clearly indicate the file is for Part II$.$

$*$ Tables presenting the ten worst$-$case execution time measurements

$*$ A graph showing the averaged worst$-$case execution times for all three collision

resolution schemes

For Python Programmers: Use $$PyCharm$$ for your IDE.

Part II$.($Optional$,$ up to $2$ extra points$)$

Comparison of Open Addressing Schemes Based on the Load Factor

The provided hash table implementation incorporates three open addressing collision

resolution methods: linear probing, quadratic probing, and double hashing. Evaluate the

performance of these methods by varying the load factor $(\backslash$lambda $)$ to $0\mathrm{.}3,0\mathrm{.}4,0\mathrm{.}5,0\mathrm{.}6,0\mathrm{.}7\backslash$lambda $\backslash$lambda $=0\mathrm{.}3\backslash$lambda $=0\mathrm{.}4,\backslash$lambda $=0\mathrm{.}5,\backslash$lambda $=0\mathrm{.}6,\backslash$lambda $=0\mathrm{.}7,$ and $\backslash$lambda $=0\mathrm{.}8\backslash$lambda $,$

O$($NlogN$),$ and O$($N$)$ algorithms$=100$ is shown below for your reference.

You must add a similar table for each input size.