Generate Random Arrays 1. Make a large dynamic array of random integers between some min and max value. a. Put this code in a function so you can get a random dynamic array by passing in 1) the min value,

2) max value and

3) array size as parameters. b. The function then returns that array (pointer) or NULL if a problem occurs. c. The array you test should be at least 20,000 elements large (probably larger). Notice you will want to use the rand() and srand() functions. That will involve including a standard library. 2. make a function to duplicate the contents of one array to another. 3. Make two new arrays identical to your first randomly generated array. 4. Make sure you free your random arrays when the code is finished with them. Include "time.h" and "stdlib.h" Call srand(time(NULL)); before getting a random number. This uses the clock time on the computer (so pretty random) to set the random number generator. A call to rand() returns a random number between 0 and RAND_MAX. How can you make sure the range is between min and max?

Can I use % (mod or remainder) to make sure a number is between 0 and some number? Let's say 20: 39%20 == 19, 40%20 == 0, 41%20 == 1. Think about the math before you code. It's not hard if you play with some numbers. For example -5 and 20....so 25 numbers in total ..... if I have a number between 0 and 25, what do I get when I subtract 5? QSort Time 5. Now that you have three identical giant arrays of integers, call the standard library's qsort function to sort the first array (qsort stands for Quicksort which is a famous/infamous algorithm that is fast but hard to understand). However, just before calling qsort get the system clock time (a call to clock()): clock_t c1 = clock(); a. On the line after the qsort call, get the system clock time again (c2). b. The difference between the two clock_t values lets you calculate is how many milliseconds the algorithm took: int functionTime = 1000.0 * (c2 - c1) / CLOCKS_PER_SEC; Note: the time() function returns a time_t value representing the number of seconds since January 1, 1970 ....please look up what the time() function does. I find epoch times fascinating). Time is normally better if you just need seconds. The function clock() is only used because we need greater precision but that means an ugly work-around. Clock time actually means "nothing" since it depends on the system. The CLOCK_PER_SEC is how many system time units fit in a second. mySort 6. Add sorting algorithm mySort a. This can be any sorting algorithm you want (within reason: bogosort is not a good idea ....you can look up what that is if you're curious). The algorithm just has to sort an array of integers (so it doesn't need to be a templated function). You could choose one of the one we talked about in the class. 7. Get the clock time before and after your mySort call. How long did it take? Put the mysort and qsort times in a comment in your code. Also, make sure your two arrays are still identical after sorting.a. I would suggest to make a compArray function to prove they are the same rather than eyeballing the values. pqSort 8. Write a function pqSort that uses the standard library's priority queue class (https://en.cppreference.com/w/cpp/container/priority_queue). pqSort adds elements to the queue one by one (you call push) and then removes the elements (pop) one by one after that. a. A priority queue is a queue that stores values in order and then removes values (dequeues or pops) from the "front" of the array. If I put the elements back in the array in the order they were pulled out, then I have a sorted array i. But notice they are sorted in REVERSE order. You will need to put them back in the array starting from the last position. b. Get the clock time before and after your pqSort call. How long did pqSort take? 9. a brief comment about what you noticed about the three sorting algorithm run times. Try varying sized arrays to see how the numbers changed. If there is no difference between the 3, try much bigger array sizes (like 500 000 or a million) Hash Table a. Hash Tables are a table / array to store values where elements (in our case: ints) are slotted into the table based on a "hash number" b. We will use pointers to those elements so that we know when a slot is empty: it will be NULL. c. Elements are slotted based on a "hash" function and a number unique to the element. d. Each element in the table can be uniquely identified by a number (this may be the object's pointer, an int value, or the numeric value of a character array). For example, your student number uniquely identifies you to the university.e. The hash is a mathematical function that consistently converts that unique number into a valid index in the table / array. 11. Add as many elements to the array / hash table as there are positions in the table. If your hash table is size 20 then add 20 elements. You should get collisions (two values are assigned the same position in the array). Count the number of collisions that occur. 12. Change your hash function. Add the same elements to this revised hash table. How many collisions occur now? 13. Add a comment below your hash function indicating the number of collisions you found in each case.