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, youll measure and predict the running times of three algorithms that solve the same problem in different ways. Deliverables:

GitHub Classroom: https://classroom.github.com/a/Bc17ge2K

Required Files: compile.sh, run.sh

Optional Files: *.py, *.java, *.clj, *.kt, *.js, *.sh Part 1: Ground Rules

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.50² GNU Bash 5.0.2³

However, Python is recommended as it is the only language I can help you with.

To make automated grading possible, you will also need to submit two short shell scripts: one to compile your submission, one to run it. Further details, along with sample submissions in all supported languages, can be found here: https://github.com/csc349fall19/asgn-samples Furthermore:

• Submit only source code files as they are. Any directories or compressed files will be ignored.
• For record-keeping purposes, you must hand in original source files, not pre-compiled files.
• You may not use any third party libraries⁴, even if they are installed on Cal Polys Unix servers.

Part 2: GitHub Classroom

In this class, youll submit your programs through GitHub, an online host for tool known simply as git. Git tracks changes you make to files so that you can easily undo or combine changes while working on a project. You should already be familiar with the basic features of git from previous classes, such as CSC 202 and CSC 203. If not, the following resources might be helpful:

• https://help.github.com/en/articles/set-up-git
• https://help.github.com/en/articles/cloning-a-repository
• https://help.github.com/en/articles/managing-files-using-the-command-line
• https://help.github.com/en/articles/pushing-to-a-remote

GitHub Classroom allows your instructors to accept electronic submissions through GitHub.

1. Enter your Cal Poly and GitHub usernames in this form: https://forms.gle/fkYfJRpyLNCtRWAs9. This allows us to determine who should get credit for your electronically submitted assignments.
2. Accept this GitHub Classroom assignment: https://classroom.github.com/a/Bc17ge2K. This will create a new repository for you on GitHub which you will use to submit this assignment, as well as provide some sample inputs and their expected outputs.

¹You may assume that the Clojure JARs are in the classpath and that the clj and clojure commands are available.

²You may assume that the Kotlin lib is in the classpath and that the Kotlin bin is in the path, for JVM-backed Kotlin.

³Not that Id recommend it this is very much not what Bash was designed for.

⁴And your submission wont have Internet access when its run, so you cannot use apt/pip/lein/npm to install them.

Assignment 1 Algorithm Analysis

Fall 2019 Due: Friday, September 27^th

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 ₁₀. 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.
2. Randomly generate a sequence of _5,020 Run the three sorts and record their running times.

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 ₅₀₀ 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 ₁₀ minutes? Consider fitting a curve to your plots in order to answer these questions.