One might argue that computer science is about scalability. It is not necessarily about asking how can we solve domain specific problems, but rather how we can solve domain specific problems efficiently as they scale.

As we will learn in CS0160, we can write many algorithms to solve the same problem and the choices we make will change the running times. The goal of this project is to demonstrate that different running times dramatically change the run-time performance of a specific task.

We will study sorting algorithms by programming, analyzing and graphing the running times of different sorting algorithms on varying sizes of data.

Getting Started

Install
Run the install script: cs016_install runtime

Running MATLAB
Type matlab into a shell to open up MATLAB and start working.

Using MATLAB
If you haven't worked with MATLAB have a look at the tutorial before you come to hours.

Hand In
Simply type: cs016_handin runtime

Algorithms

Create graphs using the MATLAB function "plot" which demonstrate the different running times of the following sorting algorithms:

Matlab Sort

Trickle Sort

	Input array A
	n ← the number of elements in A
	For integer i from 1 to n do
	    For integer j from n down to i+1
		If the element at j-1 is greater than the jth element then
		    Swap the two elements

Sababa Sort

Sababa: In hebrew it mean, shibby, cool, great, no problem, all-right.
(Matt the Emu went to Israel over the break.)

	Input array A.
	n ← the number of elements in A
	For integer i from 1 to n do
		Find the smallest element of A from i to n
		Swap the smallest element with the element of A at i

You are given Spike's code from class which he used to demonstrate the running times of various selection algorithms. Your job is to modify Spike's code to implement the three sorting algorithms discussed in this handout and to compare their running times based on the experimental results of the tests.

Make sure you throughly consider the input sizes that you choose. We have written the code for plotting the graph for you. All you need to do is type in "sorting()" on the Matlab command line. You should consider editing the variables in sorting.m to get an understanding of their effects on the running time of the algorithms.

ReadMe

You are expected to hand in a README file explaining what you have observed and identifying the running time in big-O notation of the algorithms. In order to do this, simply create a text file named "README" (you can do this in xemacs, kate, or whatever editor you choose) and save it in the same directory as your project; it will be automatically included when you run the handin script.

The majority of your grade is your ability to articulate information about your project. Your README should address the following questions:

• What are the big-O run times of the algorithms?
• How do you know based on the input sizes that you chose?
• How do the run times compare?
• Why are we interested in the log graph of the run times?
• Why do we care about running time at all?

Note: This write-up should not be any longer than a page! Keep your answers concise and to the point.

Grade Distribution

• 30% Correct implementation of the algorithms and testing code.
• 70% Your write-up in the README.

Good Luck!