Computer Science 385
Design and Analysis of Algorithms

Spring 2019, Siena College

Problem Set 3
Due: 4:00 PM, Friday, March 8, 2019 (code)
and 4:00 PM, Monday, March 11, 2019 (writeup)

You may work alone in a group of 2 or 3 on this assignment.

All GitHub repositories must be created with all group members having write access and all group member names specified in the file by 4:00 PM, Monday, March 3, 2019. This applies to those who choose to work alone as well!

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository, which will be named ps3-yourgitname, for this problem set. Only one member of the group should follow the link to set up the repository on GitHub, then others will be granted write access.


Your submission requires that all required code deliverables and a PDF file of your writeup are committed and pushed to the master for your repository's origin on GitHub. If you see everything you intend to submit when you visit your repository's page on GitHub, you're set.

Empirical Analysis of Sorting Algorithms

Your task, worth a total of 50 points, is to conduct an empirical study of sorting algorithms. We have studied three sorting algorithms so far: bubble sort, selection sort, and insertion sort. We will soon see others.

A sample empirical study, both code and writeup, is available in a GitHub repository that you are welcome to clone or fork so you can use it as a model for your own study and writeup. Suggestions for improvements to this sample study are welcome in the form of Issues and Pull Requests to the repository.

A Sorting Framework for Gathering Timings

Your first task, for 15 points, is to develop a program to perform an empirical study of the efficiency of these sorting algorithms. Your program should operate on arrays of int values. It should have command-line options to set the array size, the number of trials (to improve timing accuracy), the ability to generate initial data that is sorted, nearly sorted, completely random, and reverse sorted (use the class you wrote for the previous assignment for array population). Design your program to make it easy to implement additional sorting algorithms later.

First Empirical Analysis Study

Perform an empirical analysis study for bubble sort, selection sort and insertion sort, on an appropriate range of data sizes and distributions. Use your sorting algorithm program to generate timing data. Compare your timing results with your expectations based on our (theoretical) efficiency analysis of these algorithms. Present your results as a formal laboratory report. (35 points)


A typical submission will include the source code for the program used to generate the results, a PDF document that contains the formal writeup, and any spreadsheets or other files that include the raw data.

The formal writeup should follow the format of the sample empirical study that will be posted soon. It should have a section that includes a brief introduction to the task, including test environment information. There should then be a section for each algorithm that describes specifics of that algorithm, the theoretical expectations (including best/average/worst cases, where applicable), a summary of your timings and counts in tabular format, graphs illustrating these results, followed by more text that analyzes the results, comparing with the theoretical expectations. A brief conclusion section should summarize the study's results.