CM10228 / Programming II: Tutorial 2
This is an optional second tutorial with a couple objectives:
There are at least two good reasons to work in pairs on a problem.
is just that you learn better. Extensive research in learning has
that if you have to explain what you are doing, you will learn better
an exercise than if you don't, even if you produce the same answer on
exercise. Coming up with an answer isn't always the same as
understanding the answer, but if you talk about it you probably will
- To help you understand tree structures better by building
- to give you a feel for an important innovation in software
engineering, pair programming.
The other argument is the software engineering one. The idea is
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
of code, it's quite likely that many bugs will be caught before you
try to compile.
One thing that you need to know for pair programming is another lesson
Fredrick Brooks' "Mythical Man Month" --- there are many ways to solve
code any problem, and a lot of time can be wasted arguing about which
best. Often, the amount of improvement from this discussion may
be worth the temporal or emotional cost of the discussion. The
to this situation is to make one person in charge for the duration of a
During this tutorial, the person who is holding the keyboard will
the one who decides what to do when the two of you can't agree.
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
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
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