Week 03 Lab Exercise

• To familiarise yourself with practical aspects of computational complexity
• To practice a systematic approach to problem solving
• To apply sound scientific reasoning in reaching conclusions
• To hone your analysis skills
• To identify algorithms from their behaviour

Marks

5 (see the Assessment section for more details)

How to submit

see the Submission section

Deadline to submit

12pm Tuesday of Week 4

Submission late penalty

0.2% per hour or part thereof deducted from the attained mark, submissions later than 5 days not accepted

When to get handmarked

in your Week 3, 4 or 5 lab session (after you have submitted)

A long time ago, in a burst of enthusiasm, Richard Buckland wrote a collection of sort programs. Sadly, he forgot to give the programs meaningful names, so when he later passed them on to COMP2521 lecturers to use for this lab, he couldn't tell us which program used which algorithm. All that he could remember is that the sorting algorithms he used came from the following list:

• Bubble sort
  • bubble sort with early exit
• Insertion sort
  • standard insertion sort
• Selection sort
  • standard selection sort
• Merge sort
  • standard merge sort
• Naive quicksort
  • uses the leftmost element as the pivot
• Median-of-three quicksort
  • uses the median of the first, middle and last elements as the pivot
• Bogosort
  • randomly generates permutations of its input until it is sorted

Despite not knowing which program uses which algorithm, Richard did remember a few things about the programs:

• The programs read their input from stdin and write the sorted version of the data to stdout
• The programs treat each line of input as an item to be sorted
  • Like the Unix sort program
• There is a limit on the size of the input the programs can process (100,000,000 lines)
• The programs expect each line to start with a number, which acts as the sort key. If no number is present at the start of a line, the number will be taken to be zero.

Your task is to identify the specific sorting algorithms used in two of these programs. You will not be able to view the source code. Instead, you will have to try to identify the algorithms using only the programs' observable behaviour when sorting different data. Note that since the programs are only available in binary format, they will most likely only run on the CSE machines, so you'll have to do your work there.

In the setup phase, you will be given access to two different sort programs; each pair or individual gets a different pair of programs. The first phase of the task is to design and write up the experimental framework that you plan to use to solve the problem. In the second phase, you will gather data on the behaviour of the two programs according to your experimental design. You will then add the data to your report and analyse it to reach a conclusion on which sorting algorithm each of the supplied programs uses.

Create a directory for this lab, change into it, and run the following command:

/web/cs2521/26T3/labs/week03/setup/setup

This must be run on the CSE machines, either via VLAB or SSH. The command will set up two symbolic links in your directory called sortA and sortB which reference executable programs under the course account. It will also give you a copy of the following files, which are described in more detail below:

gen

a program that generates input data for the sort programs

timeit

a shell script that collects timing data

example-data.txt

a file that contains example input data in the format required by the sort programs

/web/cs2521/26T3/labs/week03/setup/setup --share

Provided Files

sortA and sortB

These are the sort programs you have been allocated. More accurately, these are symbolic links (i.e., shortcuts) to sort programs that are stored under the course account, but you can run them the same way as any other program. The sort programs have been described above, but in short, they treat each line of input as an item to be sorted, and they expect each line to start with a number, which acts as the sort key.

You can verify that the programs work by entering input like so:

./sortA
2 a
3 b
1 c

1 c
2 a
3 b

gen

This is a program that generates data in the format expected by the sorting programs. It takes three command-line arguments:

• N - the number of lines to generate
• order - the letter A, D or R, which indicates that the lines should be sorted in ascending, descending or random order respectively
• seed (optional) - the number that is used to initialise the random number generator. Providing the same seed will result in the same lines being generated. If this is not supplied, the current time is used as the seed.

Here are some examples of its usage (note that due to random number generation, you will get different letters):

./gen 5 A
1 lqt
2 eju
3 slq
4 hfr
5 tyw

./gen 5 D
5 obz
4 agt
3 cph
2 yfb
1 mkj

./gen 5 R
4 vlb
1 rjo
3 mbl
5 waj
2 ooy

Since the data produced by the gen program is in the exact format required by the sort programs, you can redirect its output directly to the sort programs using the pipe operator (|) like so:

./gen 5 R | ./sortA
1 vek
2 qgq
3 pkm
4 gte
5 rgn

timeit

This is a shell script that you can use to collect timing data. It takes one command-line argument, which is the sort program you want to collect data for (sortA or sortB), and measures the execution time of the program for many combinations of input size and input order. For each combination, it runs the sort program several times so that you can calculate the average runtime.

This is what the script does, as provided:

• For each input size in [10000, 20000, 40000, 80000, 160000]:
  • For each input order in [random, sorted, reversed]:
    • Run the specified sort program 5 times for this combination of size and order, and display the execution time for each run

If needed, you can edit the script to change the list of input sizes or input orders that the sort program is measured on. The file contains comments which indicate the lines that you should edit to do this.

Creating a Report

As stated in the Background section, you will need to write a report containing your methodology, results, analysis and conclusion, so you should first decide how you will write the report. You will need to submit the report as a PDF file, so we recommend using Google Docs, Microsoft Word, or LaTeX (if you are feeling adventurous).

To help you get started, a template for the report is available. You can copy the template into your report as a starting point and then fill in the sections as you go.

There is no size requirement for the report; it is the quality of the report which matters. If you want to include detailed reporting of timing results, then put these in an appendix. Your report should be clear, scientific/systematic in approach, and all reasoning and assumptions should be explicit. Make sure you ask your tutor if you are unclear about what is expected.

The submission for this lab is a report containing your experimental design and results/analysis. It should be submitted as a PDF file called report.pdf. If you are working in a pair, you must both submit the report. You can submit via the command line using the give command:

give cs2521 lab03 report.pdf

You can also submit via give's web interface. You can submit multiple times. Only your last submission will be marked. You can check the files you have submitted here.

There is no automarking for this lab. To receive a mark, you must show your report to your tutor during your Week 3, 4 or 5 lab session. You will be marked on the following:

Criteria for Experimental Design

Criteria for Results and Analysis