Question:
In part 1 of Assignment 3,
do we have to free up the memory for procedure Question:
For procedure printSet, should the output be a sideway
tree diagram, as in the one in Assign 3a?
Question:
I've a simple question about recursion and part 1 of
assignment 3. I'm reluctant to use recursion when
implementing the addElement procedure in the revised
Set class. My algorithm uses a loop statement to
descend the tree. The algorithm is fairly straightforward and simple.
My thinking is that recursion may be too sophisticated
to do something simple like moving to a leaf node.
My question: Are we required to use recursion in all
revised subprograms in the Set class?
Question:
Are we going to be graded on the amount of time we took on each
section, or is that only for statistical use? (i.e. if it ends up
taking me 120 hours to fix the bug, will that count against me?)
Question:
Instead of using two layers for recursion, could we not have a
global variable within the class to point to the current and/or
the next leaf. i.e. the global variable would would point to a
different leaf for every time the function calls itself
Function Subset (and also recSubset, which it calls) is going to
produce a subset of the present set and return it to you. (By the "present
set", I mean whatever set is currently stored in the instance variables for
this instance of the Set class.) But it needs some criterion for deciding
which elements of the present set to include in the subset it's creating.
You could use an if-statement to express some specific criterion, e.g.,
include only StreetObjects whose colour is not blue, but then your Subset
function would be very specific. If you wanted to create a subset using
some other criterion, you'd have to write another subset function.
The alternative used here is to not code in a fixed criterion. Instead
ask the caller to name a function that expresses whatever criterion they
want used. In the formal parameters to Subset and recSubset, we use a
very generic name, f, because we have no idea what sort of function will be
passed in. All we know is that it must take something of type elementType
and return a boolean answer, which we'll use to decide whether or not to
include the element in the new subset.
For an example of how to call Subset and pass in a specific function,
see the sample testing driver that I posted to the course web site on
Thursday. In that case, the function is called `odd', and it says yes
to odd-valued SimpleObjects only.
Attendance is not
compulsory; this is simply intended to be helpful.
I'm working out another suggestion for doing your testing,
and will post it on the web page.
You may wonder why have two layers -- why not just export the
recursive routine that includes the extra parameter?
One reason is that the caller, being outside the class, doesn't
have access to the root pointer, and so wouldn't be
able to make the initial call.
The starter code for your revised set module is now ready.
Click here or get it through
the Assignments and Tests page.
Note that I have indicated the subprograms for which we'll provide
bodies, but haven't provided the bodies yet. You can proceed with
the assignment and then paste those bodies in when they're available.
Answer:
For correctness, not necessarily.
For efficiency, definitely.
Answer:
Do you think that that is an appropriate sort of output?
Think about it.
Answer:
You do not have to use recursion in all the subprograms.
You are right that there are some which can be nicely
handled with just loops.
I wouldn't say, though, that recursion is too sophisticated
to use in these cases.
Answer:
The hours that you report are just for our information -- it will help us
in planning future assignments. This will have no effect on
your mark.
Answer:
It's possible to make this work, but it would be really bad style.
To get the hang of recursion, make sure that the parameters
convey everything that must be known about the data to be processed
(in this case, the tree).
procedure recSubset (r : ^treeNode, function f (e : elementType) : boolean,
var buildingSet : ^Set)
I'm not sure I even know where function f is, so I don't know what to do
with it here.
Answer:
Function f isn't defined anywhere -- it's just the name of a formal parameter
to recSubset. This is no different than buildingSet. You don't see a variable
of that name defined anywhere except here in the header to the function. Both
f and buildingSet will receive actual values when recSubset is called.
There is indeed something special about f, however. You've probably never
seen functions passed as parameters before. Here's how it works in this
example.
Answer:
That's exactly the idea. :-)