CSC349-Assignment 1 Algorithm Analysis Solved

Analysis of algorithms concerns two broad concepts: correctness and complexity. Given that an algorithm produces the correct output for any input, we are interested in the resources it requires in different situations. In this assignment, you’ll measure and predict the running times of three algorithms that solve the same problem in different ways.

Throughout this class, you may implement your assignments in one of the following languages:

         · Python 3.7.4                                           · Clojure 1.10.1[1]                                                    · Node.js 12.10.0

         · Java 12.0.2                                              · Kotlin 1.3.502                                                        · GNU Bash 5.0.23

 

Part 3: Sorting Algorithms
Recall that there exist several algorithms commonly used to solve the sorting problem, including:

· SelectionSort repeatedly selects the smallest element from among the as-yet-unsorted elements.

· InsertionSort repeatedly inserts the next unsorted element into a sorted subsequence.

· MergeSort recursively sorts the two halves of a sequence, then merges the sorted halves back together. In your programming language of choice per Part 1, implement these three algorithms for sequences of integers. Your program must accept as a command line argument the name of a file containing such a sequence, printing to stdout the results of applying the three algorithms. For example:

$ ./compile.sh

$ ./run.sh in1.txt

Selection Sort: -16, -15, -14, -7, -6, -5, -4, 0, 1, 2, 5, 7, 8, 13, 14, 15

Insertion Sort: -16, -15, -14, -7, -6, -5, -4, 0, 1, 2, 5, 7, 8, 13, 14, 15

          Merge Sort                                     : -16, -15, -14, -7, -6, -5, -4, 0, 1, 2, 5, 7, 8, 13, 14, 15

Your program will be tested using diff, so its printed output must match exactly.

Part 4: Analysis
Record the running times of each algorithm for sequences of randomly generated integers between 5,000 and 10,000 elements in length, in increments of 10. That is to say:

1. Randomly generate a sequence of 5,000 integers. Run the three sorts and record their running times. 2. Randomly generate a sequence of 5,010 integers. Run the three sorts and record their running times.

3.   Randomly generate a sequence of 5,020 integers. Run the three sorts and record their running times.

4.   …

You may certainly write a program to automate this process, however, note that this is separate from and should not be a part of the program specified in Part 3.

Plot these timing results, with the length of the sequence on the horizontal axis and the running time on the vertical axis — you should have a scatter plot with 500 points for each algorithm.

Finally, using these empirical running times, extrapolate: How long should each algorithm take to sort 25,000 elements? How many elements should each be able to sort in 10 minutes? Consider fitting a curve to your plots in order to answer these questions.


 
[1] of 3