HW2 Empirically Analyzing Algorithms

CS 350
Due 2/11 before class starts

• Collaboration: You may work in groups of up to 3 students per group. Remember to clearly indicate the group members on your HW submission.
• Submission: You should email your submission (preferably typed up in LaTeX but will also accept neatly handwritten) to cs350pdx@gmail.com
  Feel free to email to all group members on the same email so we can reply all
• IMPORTANT: Provide an email subject line with the following pattern: HWx Section xxx - Full Name, Full Name, Full Name

The answers that you provide should clearly demonstrate that you understand the assignment and should provide enough information to clearly explain your solution to a peer.

---

Assignment

In a programming language of your choice, implement and empirically analyze the following sorting algorithms as described in class:

1. Selection Sort
2. Merge Sort
3. One other sort algorithm of your choice

(Feel free to base your code on the pseudocode in the textbook or on implementations you find online, but ensure that each implementation operates on similar objects and cite your sources.)

To analyze the algorithms, you will need a method to track the time each take to process inputs and a method to generate inputs of various sizes and orderings (arrays of ints is reasonable).

You should submit the following:

1. The source code for the implementations

2. A write up including the following points:

   • Briefly describe your development process. What sources did you use for your algorithms? What programming language did you choose and why? Did you run into any difficulties with the implementation? How are you timing the algorithms? What hardware are you timing on?
   • Graph or tables of the run times of your algorithm implementations on various sized inputs. Do this with sorted and randomized inputs. Do your observations match the theoretical analysis from class? Why or why not?
   • Comparison of your results with each other. How does each fare under different testing circumstances? Given your results, in what real world situations would you favor one algorithm over the others?