Objectives: Objective of this recitation is to reinforce algorithm design and performance analysis (theoretically and practically) ideas discussed in the class and apply algorithm analysis/design technique in solving a new problem
Note: This an individual submission and no-collaboration expected.
Submission: Please carefully read the submission instructions given for each question.
1.[30 Pts] Programming Question:
In this problem you will be comparing the running time of merge sort, quick sort Insertion sort, and selection sort algorithms.
- Frist, develop three C++/C methods that implement the above four sorting algorithms described in the book. Your code should match with the exact algorithms described in the book. I have provided a supplementary document with four sorting algorithms that you need to implement here. We will use these four methods in part (b) below
- In this part, we record the running time by running the three sorting algorithms implemented in part (a) above for arrays of following sizes. Initialize the array with randomly generated double values between 100 .00 1000.00
| Array Size (n) | Insertion Sort | MergeSort | QuickSort | Selection Sort |
| 1000 | ||||
| 10000 | ||||
| 25000 | ||||
| 50000 | ||||
| 100000 | ||||
| 150000 | ||||
| 200000 |
- Plot four graphs that represents the running time with respect to the size n based on table above for the three sorting algorithms repeatedly. (you can use excel to plot the graphs)
- Compare the graphs in (c) and the asymptotic analysis based running time of above sorting algorithms. Can you conclude that asymptotic running time is a good indicator of actual performance of the algorithm after comparing the graphs in (c) and the asymptotic analysis based running time? Explain your answer.
Submission: C/C++ program with answer to (a),
Completed tables for (b),
graphs from (c), and written answer to part (d)
Make a zip file name recitation2.zip including all parts mentioned above
Reviews
There are no reviews yet.