Sorting (ginorst)

Form groups of two or three people. You should start this group activity by introducing each member of the group. You may also want to choose one person to write down the group's discussion on the provided transparency as you go so that it can be displayed on the classroom's overhead projector.

There are three parts to this activity:

developing and writing down an algorithm that others can use to sort a list of words
testing your algorithm on several scenarios
abstracting your algorithm to sort any kind of thing, not just words

Specifying an Algorithm

Each group must write an explanation of how to sort a list of words by alphabetical order. Assume that the number of words is not known in advance, but will be between 10 and 600. You are to write an algorithm in English that specifies precisely how to sort the words. This means that you must convey exactly what steps to follow: consider that another group, or the professor/computer, might use your algorithm by following the instructions literally. Thus, saying "put in alphabetical order" is too vague. The end result is a list in alphabetical order, but what procedure should you use to put them in this order?

For this exercise, you can assume that your "sorting computer" knows how to:

report if one word is alphabetically before, equal to, or after another
get any word in a list according to its absolute place (i.e., first, second, tenth, penultimate, last, etc.)
get any word in a list according to its place relative to another (i.e., before, after, next, etc.)
add a single word at a specified place in a list
remove a single word from the list
swap the positions of any two words in the list
determine if there are any words in a list
remember a number, word, or list
create an empty list

There are many words, so you may want to start by focusing on how to sort a small subset of the words. For example, a one word list is always in sorted order. A two word list is either in sorted order, or the words' order needs to be swapped. Once you understand how the simple cases works, generalize your method to work for any number of words.

To help makes things more concrete, your group will be given a set of approximately 60 flash cards. You can physically sort them in order to help you understand how to describe the process. However, to properly simulate the computer's view of the flash cards, at most two cards should ever be "face up" at any given time. Keep in mind that your physical space is important. Where do you put things while you are working on other things? For example, think specifically about how you would explain to someone, who can hold only one thing at a time, how to swap two things.

Your group should submit its algorithm on the supplied transparency.

Testing your Algorithm

When writing algorithms, it is very easy to make logical errors, i.e., doing a step out of order, doing a step too many times, doing a wrong step, missing a step, or even missing a series of steps to handle a particular case. Thus it is important to test your algorithm on a variety of kinds of lists to have some confidence that it will work for all kinds of lists.

Since it is impractical to test every possible list of words, we choose specific kinds of lists that we think will reveal possible problems. These are called boundary cases because they focus on the edges of our algorithm where we are most likely to make an error. Note, instead of building in special steps to handle every one of these cases, you should focus on creating a single, generic procedure that will work for all cases.

To verify that your group's algorithm is correct, test it against these scenarios:

a list of one word
a list of three words in random order
a list of twelve words in random order
a list of ten word that are already in sorted order
a list of ten words that are in reverse sorted order

To test an algorithm using a scenario, you must simulate it as if the sorting computer were following the directions in your algorithm, not another human in your group. In other words, you have to be very careful not to use your common sense to fill in the gaps between the steps. It turns out that a human has to work very hard to be as literal, or dumb, as a computer. This process is called hand-simulation and we will continue to use this technique throughout the semester to verify our programs.

You group should write the results of the test scenarios on a separate sheet of paper. You should also describe any changes to your algorithm that were necessary.

Adapting your Algorithm

Sorting is one of the most basic algorithms in Computer Science because it is often the difference between a fast program and a slow one. Therefore, it is common that modern sorting algorithms can sort any kind of thing that can be represented with a computer, not just words.

Once your group has created an algorithm, you should adapt it to sort new kinds of things. For example:

a hand of playing cards by suit and rank
library items by the date they are due back
CD tracks first by the name of the artist and then year published
25,000 high-school AP exams by student ID number
web pages resulting from a web search based on the number of other web pages that refer to the page

For each of these different kinds of objects, you should consider what changes, if any, are necessary in the commands your sorting computer understands. One way to characterize these changes is by determining what kinds of things are being modelled within your algorithm and what services, or behavior, your algorithm requires of the each different kind of thing being sorted.

You group should write the results of the change cases on a separate sheet of paper. You should also describe any changes to your algorithm that were necessary.

Comments?