CM10135 / Programming II: Tutorial 2

This is an optional second tutorial with several objectives:

To make certain you understand the sorting algorithms presented in class,
to make sure everyone is feeling comfortable programming in Java, and
to give you a feel for a relatively recent innovation in software engineering, pair programming.

There are at least two good reasons to work in pairs on a problem. One is just that you learn better. Extensive research in learning has shown that if you have to explain what you are doing, you will learn better from an exercise than if you don't, even if you produce the same answer on that exercise. Coming up with an answer isn't always the same as really understanding the answer, but if you talk about it you probably will understand it.

The other argument is the software engineering one. The idea is that most development time is spent not so much in writing new code, but in debugging it & trying to get it to work. With two people looking at one set of code, it's quite likely that many bugs will be caught before you ever try to compile.

One thing that you need to know for pair programming is another lesson from Fredrick Brook's "Mythical Man Month" --- there are many ways to solve or code any problem, and a lot of time can be wasted arguing about which is best. Often, the amount of improvement from this discussion may not be worth the time or emotional cost of the discussion. The solution to this situation is to make one person in charge for the duration of a project. During this tutorial, the person who is holding the keyboard will be the one who decides what to do when the two of you can't agree. Don't worry, you'll get to take turns holding the keyboard.

Again, you will be learning more about agile programming methods in your second year. This tutorial (your last that's not just about coursework) is exploiting the methodology to help make sure everyone really understands the sorting algorithms, and that everyone is really happy developing java code.

What to do:

Choose a partner.
Choose which partner goes first at the keyboard. You're going to be doing two sorting algorithms, so you each get to code one.
Create some objects to sort. Create a class with some key attribute you will sort on. If you can't think of anything you like better, then create a class "Child" which has an attribute "age" that you can sort on.
Create a "main" function for your class that takes an argument that is a length and creates an array full of your objects with different key values.

You might want to use the "random" function in the math library. It will give you a value between 0 & 1. To make that into a child's age, multiply it by 18 (now the number is between 0 & 18) and cast it to an integer (you should probably use java.lang.Math's round to be explicit about what happens rather than just a cast). That way you can easily test your sorting algorithms over a variety of values.
Make sure your main function can print out the key values of the objects in the order they appear in the array.

Create a sorting method for your class, using either selection sort or insertion sort (you choose).

First discuss the algorithm with drawings & make sure both partners agree on how it will work, and what variables will be needed.
It's not cheating to look at the course notes, but it is cheating to just download a java version.

Give the other partner the keyboard.
Run your sort function from the main program. Make sure it works for odd & even numbers of objects, as well as empty arrays and arrays with only one thing in them.
Create a quick sort for your class.
Run the same tests over your quick sort.
Final bonus thing to do (you can change the keyboard again now if you want, up to you) --- look at how conventional java programmers (not computer scientists) would be doing this.

Put your objects into an ArrayList, and then figure out how to use Collections.sort() to sort them.

To do this properly, you should probably implement the interface Comparable for your class, using your attribute
For example, if you used my default, order Child objects by age.

You might want to look at the code for Collections.sort() too.
You may also want to look at java.util.random. The way I told you above to get a random integer will work in any language, but java.util.Random is slightly easier to use because of the interface, and more importantly is a better random number generator.

NB Be sure both partners save copies of all the code you write -- you might want to refer to it some time in the future.

page author: Joanna Bryson
20 Feb 2005