> the write up on notes from the lecture over spring break references two ways to do
>this problem,
> basically either build the tree or don't. s one of these methods much harder than
>the other?
> i have been trying to write the program without actually building the tree..but
>nothing really
comes
> out in the proper order once i get 5 or 6 lines deep. so i tried to build the tree,
>and this is
> proving equally difficult.
> can you tell me, is it necessary to 'walk through' the insertion sort more than once
>(like once
for
> each possible permutation) to generate the decision tree or should once be
>sufficient?
If you haven't first solved the problem using a decision tree, then the method
where you don't use a decision tree is much and much harder (I think). Once you have
solved the
problem by using a decsion tree, then the other method will be much easier.
The decision tree has a shape like this (this is for 3 variables) --
a < b?
/ \
/ \
/ \
b < c? a < c?
/ \ / \
/ \ / \
abc a < c? bac b < c?
/ \ / \
/ \ / \
acb cab bca cba
At each internal node you have a test (question).
Left = yes, right = no.
At the leaf nodes you have all the permutations.
Note that this tree is isomorphic to the layout of the if-else statements:
if (a < b)
{ // go left
if (b < c)
{
// abc
}
else
{
if (a < c)
// acb
else
// cab
}
}
else
{ // go right
// same as above with 'a' and 'b' swapped
}
[For those who want an extra challenge: instead of
else
{
if (TEST)
{
...
}
else
{
...
}
}
let your program output:
else if (TEST)
{
...
}
else
{
...
}
// end of extra challenge]
So once you have the tree, you can do a pre-order traversal, and when visiting a node
you print out
either the test or -- when it's a leaf node -- the final printf statement with the
ordered
variables.
So, then the problem is, how to generate a tree. It may help to think of a program
that is able to
play the 20-Questions Game. You think of an animal and the computer has to guess what
you are
thinking of.
One way to implement this is by using a binary tree, with questions at all internal
nodes, and
knowledge at the leaves. In the beginning the program doesn't really know anything,
and will always
start by guessing "cat" (for instance).
During play the program will accumulate questions and knowledge.
C - Think of an animal... (and hit a key)
H - (hits key)
C - Is it a cat?!
H - no
C - I give up! What is it?
H - a dog
C - How does a cat differ from a dog?
C - A cat ...
H - purrs
First the computer's tree of knowledge only had the node [cat].
But now the computer can update it's tree:
does it purr?
/ \
cat dog
C - Think an animal... (and hit a key)
H - (hits key)
C - Does it purr?
H - no
C - I know! It's a dog!
H - no
C - I give up! What is it?
H - a rabbit
C - How does a rabbit differ from a dog?
C - A rabbit...
[note that this program needs some rudimentary natural language parsing]
H - is cuddly
Now the tree becomes:
does it purr?
/ \
cat is it cuddly?
/ \
rabbit dog
In a similar way you can build a decision tree for sorting: start with a tree with
only one node
[abc]. Now insert each possible permutation P into the tree,
and each time replace one leaf node N by a test-node with the nodes N and P as
children.
E.g. if the second sort-order you insert is "acb", then [abc] becomes
b < c? <- how does abc differ from acb
/ \
abc acb
To insert the next string (representing a sort-order), for instance, "bac":
is b < c in "bac"? yes, so go right
we arrive at a leaf node ("abc"), so make a new test:
how does "abc" differ from "bac"? a < b
so we get:
b < c?
/ \
a < b? acb
/ \
abc bac
When all permutations are inserted, you have a decision tree (which happens to be the
insertion-sort
decision tree -- I think it doesn't even matter in what order you insert the
permutations, but I
haven't checked this).
Hans
