Each question was marked out of 20, for a total of a maximum of 100
marks for
the paper.
A table giving the marks for each student for both term-time test, but with students given only by examination number, can be found here.
As this table shows, the test was extremely poorly done. If most people attended the lectures, worked on the lab exercises in the week they were set, read the notes, and in general put in the amount of effort this course requires, the blame for the poor performance might fall on the lecturer. However, in the second half of the course lecture attendance was extremely poor - at times less than 20% of those registered for the course. Few people seemed to be putting in any serious effort into the lab exercises. When I was in the lab towards the end of the term, there were sometimes just two or three people doing that week's exercise. I am happy to take comments on this, either by email or through the discussion forum, but unless students on this course can convince me otherwise, I do think the main cause for failure was just not putting in the amount of effort required.
Below is some comment on each of the questions.
A common mistake was to say that a binary tree is ordered if "the root of the left branch is less than the root item and the root of the right branch is greater than the root item". This is not the case, what is required is that every item in the left branch (not just the root) is less than the root item, and every item in the right branch is greater than the root item. It is also necessary to say that both branches must also be ordered in the same way.
The question asked for an informal explanation of how an ordered binary tree is used to maintain a set of objects. This required some exlanation of how the set operations: add, delete and membership test are represented with trees. Many people missed off this part altogether.
List.
The lecture on this concept was very poorly attended, and I saw almost
no-one doing the exercises that were set (in week
10)
on this topic. Doing these exercises was an essential part of learning
this
material.
Many people answered this question as if it were on linked lists.
The introduction to the question made clear what methods are available
on
List objects and said that you could assume nothing else
about them. It ought to have been obvious therefore, that an
answer which didn't use these methods but instead assumed that
List objects had public fields called first
and next could not possibly be correct.
Some people who did understand that linked list data structures and List
objects are not the same thing failed to appreciate the point that was
made
in the lectures and notes that List objects of the form
we
have used are immutable. A major problem was to assume that
l1.cons(n) will change the object referred to be
l1 so that the list it represents has n
added
to
its front. In fact, as the question itself states, the cons
method returns a new list object. So, for example,
l2=l1.cons(n) does not change the list referred to by
l1 but does make a new List object which
represents that list with n added to the front, then sets
l2 to refer to that new object. The effect of changing
the object which l1 refers to is achieved by the
statement
l1=l1.cons(n). This doesn't actually change any object,
rather the call to l1.cons(n) causes a new object to be
created, and the assignment causes l1 to stop referring
to what it used to refer to and start referring to this new object.
Quite a common error was to confuse the == and =
symbols. The double equals symbol == is used either to
test that two numerical values are equal, or that two object references
refer to the same object. The single equal symbol =
is used for assignment. The statement a=b causes the
value in
b to be copied into a writing over the old
value of a if they are of a numerical type. Otherwise, it
causes
a to stop referring to what it used to and start referring
to the object that b refers to.
A few people answered this question as if List
object were
the same thing as arrays and so list[i] would refer to
the ith item in the list referred to by list.
This suggests that they have paid no attention to any of the
material in the second half of this course.
Would a correct approach to this question have been to memorise the code given in the notes and reproduce it? No. Memorisation is not a good learning technique. If you understood the concept of fields within an object manipulated by the methods of an object, and if you understood linked lists to the point of knowing how to move a pointer to remove the front item and add a new item to the back through a pointer to the back, you should have been able to work out the answer by knowing the concepts. In general, memorising things you don't understand is a difficult task, it is easier in the long run to understand and then use your understanding. As I put it once, one way to learn how to drive from A to B would be to memorise all the hand movements and foot movements a driver makes to drive a car from A to B. But a better way would be just to learn the basic concepts of driving. Then from those concepts you could drive from A to B as just one aspect of being able to drve from any starting place to any finishing place.
Part c) was answered so sloppily in many cases that it was
hard to
understand if the person knew the answer and just couldn't express it
very well, or didn't know the answer and was just waffling. However,
quite a few people did manage to indicate they knew that to join two
linked lists you had to change the next field of the
last cell of the first linked list to make it refer to the first
cell of the second linked list. In fact, since linked lists are
represented by pointers to their first cell, you could just say that
you
have to change the next field of the last cell of the
first linked list to be equal to the second linked list (this would
then
cover the case when the second linked list is empty). However, many
people
omitted to say how you get to the last cell of the first linked list.
Since
linked lists are represented by pointers to their first cell, part of
the
algorithm to join them destructively involves moving a pointer down the
first
list until it points to the last cell. Note that it is incorrect to say
(as
quite a few did) that you have to "make the next field of
the
last cell of the first list point to the first item of the second
list". This
is because "the first item" refers directly to the item held in the first
field of the first cell of the list, and that it not the same
thing
as the cell itself.
Marks were lost in part d), as in the other parts, by sloppy writing and incorrect use of terminology. There seemed, however, to be a reasonable general understanding of the stack and reverse technique, even if it wasn't always well expressed.
Set, but all of them had to
provide
the set operations add, delete and
member which appear to the front-end code that makes
use of them to operate in the same way. So we had to show how a
particular value of a set as the front-end saw it could be
represented by a setting whatever data structure, array and count, or
linked list,
or tree, and so on, appeared inside the object that represented the
set.
The same applies with sequences, which is what question 5 was about.
We have the abstract concept of a sequence as a list of objects where
the particular order in which the objects appear in the list matters,
and where there is an insertion point. The operations on a sequence
are to add a new item at the current position of the
insertion point,
to delete the item at the current position of the
insertion point, and to
move the insertion point forwards and backwards.
You saw this in the
week 6 exercise, which presented a sequence maintenance program.
Whatever data structure
you chose to put inside the class representing sequences it had to be
such that the
public methods coule be written to manipulate it and so provide the
operation of
the sequence manipulation program that was required.
Many people in answering this question chose to answer it as if it were "choose three data structures at random and describe them". Either no attempt was made to say how the data structure chosen could represent a sequence, or the attempt that was made indicated a misunderstanding of the idea of abstract data types as the data structure chosen could not represent sequences.
Stacks, queues, ordered binary trees and arrays of booleans were all examples of data structures quite a few people chose to answer this question where it ought to be obvious they are not suitable implementations of sequences. A stack is a list with an insertion point fixed at one end, while a queue is a list with an insertion point fixed at one end and a deletion point fixed at the other. So how could either possibly represent the concept of a list with an insertion/deletion point that can be moved around? With ordered binary trees and arrays of booleans representing sets of integers, there is no concept of the items in the representation having been entered in a particular order. So how could they possibly represent a sequence where the order in which the items are entered is part of the concept of the abstract data type?
Again, there was no trickery involved in this question, and the
answer ought to have been clear to anyone who attended the
relevant lecture and/or read the relevant set of notes (here)
since all it involved was re-iterating what was in that lecture and
those
notes.
The three data structures which it was spelt out in the notes and
lectures that could be used to represent sequences were a partly filled
array with two indexes (one to give the position of the last cell
currently counted as data, the other to give the insertion point), a
doubly-linked list with a pointer to the cell representing
the current insertion point, and two singly-linked lists where
one represents the data before the current insertion point and the
other represents the data after it. A fully-filled array with an
integer giving the current insertion point was another acceptable
answer, since this was given and explained as the solution to the lab
exercise on building a constructive implementation of sequence