# Design and Analysis of Algorithms - Programming Assignment

Budget $10-30 USD

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.

## Awarded to:

Hi, I am experienced C++ programmer with solid background with algorithms and data structures. I have gained this knowledge competing in various programming contests. I can implement all well known sorting algorithms ( More

## 8 freelancers are bidding on average $56 for this job

Hello sir, I have already implemented quick sort algorithm using C++. I just need to apply your random dataset and calculate the time. Please contact for more. I can do this within 3 hours. Thank you

Hi, I’ve carefully gone through your job post. I have more then 8+ years experience in artificial intelligence development.I am very much interested in your project with all of your requirements. I feel very confiden More

I am Network Security certified and always on the lookout for training and new trends in the technology. I take direction well and can complete a heavy workload and complete projects under minimal supervision. As a d More

Hi, I can do your assignment. I propose to do it in Python, since this way the visualization is much more comfortable and the explanation how to run it is much easier than in c++.

I have good academic experience and excellent skills to complete project. I am okay to adapt to new requirements.