Design and Analysis of Algorithms - Programming Assignment

You are to use Quicksort to sort N randomly generated integers and then analyze various characteristics. The project will have two parts, one for the basic implementation of the program that sorts the integers, and second for analyzing what you see in terms of performance. Part A) Desired Program Behavior: 1) User is prompted to enter a value for N (for number of integers) as input 2) The program generates N integers which are either (a) sorted in the increasing order, or (b) All integers are picked randomly with a uniform distribution from the range [0, MAX_RANGE]. Use MAX_RANGE = 10000. For part (a) in addition to N, the program should also ask an input X (a positive number) from the user and set the first element of the array to N+X, the second element to N+2X and so on (this will generate an increasing sequence of N numbers numbers). 3) The program sorts these N integers using Quicksort and Randomized Quicksort and outputs a file [login to view URL] with original and sorted values. 4) The program also outputs the computation time T(N) for sorting N integers. Be sure that this time includes only the computation time and not the time spent interacting with user and or generating the integers. You may use either python or C++ as a programming language for implementation of Quicksort and Randomized Quicksort. However, this program should be demonstrated to run on the CS Linux servers and should come with instructions for running (how to compile, how to execute etc.) it on those servers in the form of a README file. Adequate comments in the code are expected. Part B) (1) Compute average (over five different runs) running time T(N) for four different N values, N = 10, 100, 1000, 10000, 10000. Integers are to be picked randomly from [0, MAX_RANGE] (Part A.2.b above, i.e. input array is random). For example, for N = 100, run your program “five times” to get five values of T(N). Then take the average of these readings to get average T(N) for N = 100. (2) Repeat (1) but this time use Randomized Quicksort to compute corresponding running time T’(N) for N = 10, 100, 1000, 10000. (3) Repeat (1) using Part A.2.a as above (i.e., input array is sorted) to compute corresponding running time T’’(N) for N = 10, 100, 1000, 10000. (4) Repeat (3) using Randomized Quicksort to compute corresponding running time T’’’(N) for N = 10, 100, 1000, 10000. (5) Plot T(N), T’(N), T’’(N), T’’’(N) along with the functions theoretical bounds O(N) and O(N^2) (along y axis) against for N along x axis for four different values of N. Note that running time of Quicksort will always be O(N log N) or O(N^2) depending on average case or worst case behavior therefore it will always be bounded from above by c1N^2 for some constant c1 and bounded from below by c2N for some constant c2. The goal of the plot is to visually see this behavior. To graphically show this behavior you might need to rescale x axis and y-axis values. For example, one possibility is to plot N’=N/100 along x-axis and along the y-axis plot N’ and (N’)^2 as the lower and upper bounds. Now, rescale the actual run times (by appropriately dividing all run times by a suitable chosen constant) such that these rescaled run times lies in between the lower and upper bound plots. Also, present the results in Table format, where rows of the tables will indicate different N values and columns will indicate T(N), T’(N),T’’(N) and T’’’(N). Comment on the asymptotic running times of T(N), T’(N), T’’(N) and T’’’(N) in comparison to the other functions (O(N) and O(N^2)) and explain your reasoning in detail. Check the attached original document. Note: As this assignment depends on quicksort, a common algorithm, it is OK ro use code snippets from other sources if you include and cite the source in the report. When this is done properly I will be the sole owner of the code. This means you CAN NOT resell or REUSE to Similar request. Like another programming assignment. I can pay up to $50. Thank you.