Assignment 3 questions

[Boris Gjenero]

I have some questions about the assignment:

- How am I supposed to put values into the tree nodes and do comparisons
between them? One possible approach would be to not put values in the
tree for solutions to 1 and 4 and just include a virtual comparison
function. Then subclasses could add a value of some type and define the
comparison function appropriately for that type. Is this what's
expected?

- What is expected with the subclasses in 2 and 5? Do I just create a
subclass for dealing with some specific data type or do I have to make a
subclass that does something else with the tree?

- What about the sentences talking about O() times for operations? Are
those just comments or do I have to explain them and/or prove them.

--
| Boris Gjenero <bgje...@undergrad.math.uwaterloo.ca> |
| Home page: http://www.undergrad.math.uwaterloo.ca/~bgjenero/ |
| "Luke, you're going to find that many of the truths we cling to |
| depend greatly on our own point of view." - Obi-Wan Kenobi, ROTJ |

[Stranger]

On Wed, 11 Mar 1998, Boris Gjenero wrote:

> I have some questions about the assignment:
>
> - How am I supposed to put values into the tree nodes and do comparisons
> between them? One possible approach would be to not put values in the
> tree for solutions to 1 and 4 and just include a virtual comparison
> function. Then subclasses could add a value of some type and define the
> comparison function appropriately for that type. Is this what's
> expected?

remember the "class envelope" that was discussed in one of the lectures?
if you knew the type of the values being stored in the search tree, there
would be no problem. so, suppose you define your search tree to only work
on one particular type (an envelope class, for example). then you can go
ahead and put these envelopes into the tree nodes without much difficulty.
if your search tree works on envelopes, then it will work on envelopes
with integers in them, or reals in them...

> - What is expected with the subclasses in 2 and 5? Do I just create a
> subclass for dealing with some specific data type or do I have to make a
> subclass that does something else with the tree?

this is only my interpretation, but i think the subclasses we define in
2 and 5 are supposed to demonstrate the functionality of their
super-classes. i don't think we are expected to do anything out of the
ordinary with our searchtrees. the assignment says to show how to do
sorting with the superclasses. hopefully haveing a couple of different
subclasses that each sort different type of data will be sufficient.

> - What about the sentences talking about O() times for operations? Are
> those just comments or do I have to explain them and/or prove them.

in number 5 the O(n log n) specifically states "this sort" so i think
that's there to impose a bound on what the sorting subclasses will do. the
same restrictions are probably meant to apply to the subclasses in 2 as
well.

[Gordon V. Cormack]

In article <3505D94F...@undergrad.math.uwaterloo.ca>,

Boris Gjenero <bgje...@undergrad.math.uwaterloo.ca> wrote:
>I have some questions about the assignment:
>
>- How am I supposed to put values into the tree nodes and do comparisons
>between them? One possible approach would be to not put values in the
>tree for solutions to 1 and 4 and just include a virtual comparison
>function. Then subclasses could add a value of some type and define the
>comparison function appropriately for that type. Is this what's
>expected?

Yes.

>
>- What is expected with the subclasses in 2 and 5? Do I just create a
>subclass for dealing with some specific data type or do I have to make a
>subclass that does something else with the tree?

Just include the field and whatever else you need pertaining to the specific
data type.

>- What about the sentences talking about O() times for operations? Are
>those just comments or do I have to explain them and/or prove them.

If it isn't obvious that your algorithm meets the time constraints add
comments to explain.
--
Gordon V. Cormack CS Dept, University of Waterloo, Canada N2L 3G1
gvco...@uwaterloo.ca http://cormack.uwaterloo.ca/cormack