CM10228 / Programming II: Tutorial 2

This is an optional second tutorial with a couple objectives:

To help you understand tree structures better by building one, and
to give you a feel for an important 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 code & 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 Brooks' "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 temporal 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 both get to take turns holding the keyboard.

You can do this tutorial in any language you want, but if you do it in Java you might be able to reuse some of the code you write in a coursework.

The problem:

Create a random list or array of 64 items. Sort them into a tree. For the original list, see how many nodes you have to search for each item, so you can count the average search.

What to do:

Choose a partner. Make sure you agree what language to use & who should go first.
Choose which partner goes first at the keyboard. When the first hour is up, switch who types.
Create a tree-node object. Each node will have a left & right link, and a value. Initialise these sensibly.
Create a method startTree which just returns a node when handed a key value.
Create a method sortNode which takes a value & either creates a child or, if the child exists, calls itself recursively via that child.
Create a main function

Create a list or array unsort with 64 random values.
generates a tree from the first value
sorts the rest of the values into the tree.

Write a function searchTree that returns a node that holds a key if it exists, else null (or nil).
Let's see how well our complexity expectations are met.

Write a function countSearchTree that counts how many nodes you have to search until either finding a node or being sure it's not there.
Run countSearchTree on every value in unsort. What is the average number of steps?
Run countSearchTree on every value in unsort + 0.37. What is the average number of steps?

If you finish early, you can think about some modifications:

write deleteNode. Test it by deleting one node, then making sure all 63 of the others are still there & findable.
another kind of tree only stores values at the leaves. rewrite sortNode and deleteNode to be like that, and run your checks again. Are there any advantages to this kind of tree?

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
17 Feb 2010