Algorithms and Data Structures 2003: Term-time Test Results

The test was marked out of 100, 20 marks for each of the five questions. The standard Queen Mary grading system was used, so 40% is the pass mark, with 40-44 being a grade E, 45-49 a grade D, 50-59 a grade C, 60-69 a grade B, and 70 or more a grade A.

The results were very disappointing. In fact over half of those who sat the test did not pass it. This ought to serve as a warning to all students registered for the course (except the few who passed the test with good marks), that you will need to put a great deal more effort into this course if you are to pass the exam in May. You can find a spreadsheet with the results here.

I will go through the questions below, giving answers, and comments on how the question was answered by those who sat the test.

Question 1

Anyhow, here's part a) of the question:

"Write a Java static method which takes as its argument an array of integers and two integers and changes the array destructively so that all occurrences of the first integers are changed to the second."

An example was given that if the integers are 7 and 8 and the array is:

the array will be changed to:

Please note that this array, with the two numbers 7 and 8 were only given as an example to show just one way in which the method you write should operate. You were not meant to write code that could only change 7 to 8, or only deal with an array of length 11 just because the array given to illustrate the method was of length 11. Your method should deal with any array and any two integers passed as argument. Writing code that mentions the number 7 and 8, as quite a few students did, shows a major failure to understand the principle of abstraction (i.e. moving from specific examples to general cases), which underlies a lot of what Computer Science is about.

When asked to write a method, the first thing to consider is its signature. All methods have to be given a return type. However, if a method does not return a value, its return type is given as void. Destructive methods don't return a value, they have their effect by changing the value of an object they are given as an argument. All methods must have a name; no name was mentioned in the question, so we can just make one up, say substitute. The method signature has the arguments the method takes in rounded brackets following its name. Each argument is given with its type and the name you have decided to use for it in the method. The question makes clear the array takes three arguments: an array of integers and two integers. The type for an array of integers is int[]. A convention often observed is that array arguments are called a, and integers arguments are called m and n. So this gives us the following as the signature for the method that answers this question:

static void substitute(int[] a,int m,int n)

static void substitute(int[] a,int m,int n)
{
 for(int i=0; i<a.length; i++)
    if(a[i]==m)
       a[i]=n;
}

A rather strange mistake that was made by quite a few students was to write code that not only changed all occurrences of the first integer to the second, but also changed all occurrences of the second integer to the first. If that is what the question had intended, it would have said that, but it didn't.

Some students seem to feel it is necessary to have a { and a } around the body of every for loop, and every if statement. In fact it isn't necessary to have { and } around a body that consists just of one statement. My preference is to leave them out in this case, since I feel they make the code look cluttered. But they don't actually affect how the Java code runs, and I know of at least one text book that suggests it's "good practice" always to use { and }. If you insist on doing so, you would get the answer below to part a) of question 1):

static void substitute(int[] a,int m,int n)
{
 for(int i=0; i<a.length; i++)
    {
     if(a[i]==m)
        {
         a[i]=n;
        }
    }
}

My preference with { and } is to put the opening { on a new line, and the matching closing } below it. The ONLY OTHER ACCEPTABLE LAYOUT OF BRACKETS is to put the opening { at the end of the line which heads the block, and the closing } indented by the same number of spaces as that line. This would lay out the above code as:

static void substitute(int[] a,int m,int n) {
 for(int i=0; i<a.length; i++) {
     if(a[i]==m) {
         a[i]=n;
     }
 }
}

So, now lets us consider part b) of question 1), where you are asked to write a method that performs the same operation as part a) but constructively. This means you create a new array that represents the changes, but you don't actually change the old array. In this case, the method returns an array of integers, so it has return type int[]. It takes the same arguments as in part a). This is so basic there is really no excuse for not getting this part right and not even being able to write the correct signature, which is:

static int[] substitute(int[] a,int m,int n) 

int[] b = new int[a.length];

Here are some things to note, all of which are based on mistakes encountered many times in answers to this question:

1. Whereas the length of a Java string str is given by str.length(), there is no () when we are getting the length of an array.
2. There is no Java keyword array, and this word plays no part in the declaration of array variables or creation of new array values. If we ever use this word, it will only be because we decided to name an array variable array rather than, say, just a.
3. You put the type of a variable alongside it when you declare that variable as a parameter to a method or as a new local variable in a method, or as a field of a class. You do NOT put a type next to a variable in any other circumstances e.g. you do not do so when using that variable as the argument to a method call or returning it as the return value of a method.
4. When you want to create a new array of the same length as array a, assuming the base type of a is int you write new int[a.length] and not new int[a.length-1]. The last cell of the new array is indexed by a.length-1, yes (e.g. b[a.length-1]), but the number of cells in the new array is a.length with indexing starting at 0.
5. Java is case sensitive. This means it matters whether you use a capital or lower-case letter. So, for example, there is no such Java keyword as If, there is only if. The primitive type of integers is int, it cannot be written Int.
6. The key-word return means "stop executing this method immediately and put the value given next as the result of the method in the code where it is called". Do not ever use return unless you intend to terminate the method at that point.
7. Reading a value from the screen is a completely different thing from taking it as a method argument. Writing a value to the screen is a completely different thing from returning it as the result of a method. When you are asked to write a method which takes some values and returns some value, you are not being asked to write code that reads and writes things.

static int[] substitute(int[] a,int m,int n)
{
 int[] b = new int[a.length];
 for(int i=0; i<a.length; i++)
    if(a[i]==m)
       b[i]=n;
    else
       b[i]=a[i];
 return b;
}

Now here is part c) of question 1):

"Write a Java static method which takes an array and an integer and returns an array consisting of all those elements of the original array less than the integer in the order in which they occurred in the original array".

The example given is that if the method has the same array for its argument as above, and its integer argument is 6, the array returned is:

This is a little more tricky, as the array that is returned from the method is not of the same length as the argument array. Also, the numbers are not in the same positions. For example, the number 4 is in cell a[5] if a is the name of the original array, but is put in cell b[2] of the array that is returned if b is that array's name.

The big problem is that we don't know at the start what will be the size of the final array. The solution I prefer is to create a temporary array of the maximum possible size, which is the size of the original array. Then those numbers to go in the new array are copied into it. It is necessary to keep two indexes, one for positions in the argument array as we go through its cells one by one, one for positions in this new array as we copy only some of the integers from the argument array into it. The final value of the second integer is the actual size of the array that needs to be returned. We then create a new array of that size and copy the numbers from the temporary array into it. This is returned as the result of the method. If we just returned the temporary array as the result, which is what a lot of people wrote code that did, the array that would result would be:

rather than what was required.

Here is my code which answers part c) of question 1):

static int[] filter(int[] a,int n)
{
 int[] temp = new int[a.length];
 int count=0;
 for(int i=0; i<a.length; i++)
    if(a[i]<n)
       {
        temp[count]=a[i];
        count++;
       }
 int[] b = new int[count];
 for(int i=0; i<count; i++)
    b[i]=temp[i];
 return b;
}

Question 2

and draw the state after the execution of some code.

The diagram above, which is what was given on the test paper, shows how a cells and pointers diagram for linked lists should look. Remember that pointers come from individual fields of cells, in our linked list example shown as the right hand part of the cell. But they point to whole cells.

A lot of people gave answers to this question which showed cells linked with pointers, but did not show where list1 and list2 pointed to. It is necessary to show this, even if there has been no change - you need to show that you know there is no change. It is also very important to show where cells are shared. If the setup of some cells and pointers system is that two list variables point to structures which share some cells, then that is a different set up from one where the two list variables represent the same lists but don't share cells. You need to demonstrate that you understand this. It is also important when giving an answer to this sort of question to show clearly which is your final answer, and which is your working out. For example, if a pointer is changed to point to another location, a diagram which shows it pointing to the old location and the new one is useless, it is not clear what you mean, and might suggest that you believe that pointers can point to two different places at the same time (which, of course, they can't). One more thing, if nothing points to a cell because what used to point to it has been altered to point to something else then don't draw that cell in your diagram, as it is no longer part of the cells and pointers system in question.

Note that in all cases (assuming we are dealing with linked lists of integers)

something.first = ...

something.next = ...

Part a) of question 2) asks what happens to the initial situation when

list2.next.next = list1.next;

It means that list2.next.next is set to point to the same cell that list1.next points to. It is essential to show the cell sharing this leads to. Note that since nothing points to the cell list2.next.next used to point to (which contained the number 6), that cell is not drawn as part of the solution.

Part b) of question 2) asks what happens to the initial situation when

for(ptr=list1; ptr.next!=null; ptr=ptr.next) {}
ptr.next=list2.next;
list1.next.first = 10;

Part b) of question 2) asks what happens to the initial situation when

list2 = list2.next;
for(ptr=list1; ptr!=null; ptr=ptr.next)
   ptr.first = ptr.first+list2.first;

The answer to part c) of question 2) is:

Question 3

Write a static method which takes a linked list of integers and an integer n as arguments and multiplies all the integers in the linked list by n (performing the operation destructively).

As before, the first thing to do when confronted with a question that asks you to write a method is to think what the method signature is. As with part a) of question 1), the fact that the work is to be done destructively indicates the method return type should be void. The work of the method is done by changing the data structure it takes as an argument. The question states clearly that the method has two arguments, a linked list of integers and an integer.

Although we discussed the abstract data type List later in the course, this is not a question about that type. In general, when asked to answer a question involving writing Java code, you should not assume the existence of any class or method which is not built into Java, unless it is mentioned in the question. Therefore, in this question you can make use of the type Cell but not of the type List. A linked list is made up of objects of type Cell linked together, therefore its type is Cell. It is manipulated by directly accessing the fields of Cell objects, as we did in question 2). This is different from writing code dealing with objects defined by the List class we gave later, where they can only be manipulated by the methods which are defined as part of the List class.

So the signature for the method asked for in part a) of question 3) is:

static void mult(Cell list,int n)

The code for destructively altering the list uses the standard technique of a pointer going through the cells of the list one at a time. If we change one of the fields of the cells, we will cause the list of which that cell is part of to be altered permanently, i.e. we have made a destructive change. Here is code to answer part a) of question 2:

static void mult(Cell list,int n)
{
 for(Cell ptr=list; ptr!=null; ptr=ptr.next)
    ptr.first = ptr.first*n;
}

Quite a few people attempted to answer this question with code which made no sense in the context of this question, but looked like they were trying to recall some code that used linked lists that they remembered from the lectures or notes. This is an indication of that pitfall I warned you about: confusing memorisation with learning. It won't work with most computer science, certainly not with programming. It is like learning to drive (you will note I like to make analogies which compare learning to program with learning to drive) not by learning all the various manoeuvres and understanding when to use them, but instead trying to memorise the exact set of manoeuvres that take you from one particular place to another particular place. If you don't understand a piece of code, but are writing it down because some trigger word in the question brought it to your memory, you have the wrong approach, and are very likely to get it wrong. Whenever you write code to answer a question in a test, you should understand the code you are writing and be clear in your mind what it does and why it solves the problem that was set.

Part b) of question 3 asked you to write a method that performs the same operation as part a), but constructively, that is returning a new list which represents the change without changing the argument list.

So any answer to this question would need to create a new cell to match each of the cells of the original list, but with its integer multiplied by n. No change at all should be made to the original list. The obvious way to do this is to use recursion, since there is a clear recursive way of describing what we want that translates directly to code:

"The multiplication of all the elements of a linked list by n when the list is null is null. The multiplication of all the elements of a linked list by n otherwise is a list whose first cell contains the integer of the first cell of the original list multiplied by n and whose rest is the rest of the original list multiplied by n".

The underlined part above is, of course, a restatement of the entire problem, hence can be achieved by a recursive call. This gives the following as the answer to the question:

static Cell mult(Cell list,int n)
{
 if(list==null)
    return null;
 else
    {
     Cell newnext = mult(list.next,n);
     return new Cell(list.first*n,newnext);
    }
}

The return type for this method is Cell because it returns a new linked list value, and as the question stated, linked lists should be represented in the form given in question 2.

Solving this problem this way ought to be the obvious way to do it, once you are used to using recursion it should be very simple. However, most people who attempted this question tried to do it using iteration. The fact that nearly everyone who attempted an answer using iteration made mistakes that meant their code would never work as intended indicates that this is a much more complicated way of looking at it. However, there is an iterative way of solving it similar to the iterative way given in class for copying a list. Here is the iterative solution to the constructive list multiplication problem:

static Cell mult(Cell list,int n)
{
 if(list==null)
     return null;
  else
     {
      Cell list1 = new Cell(list.first*n,null);
      Cell ptr,ptr1;
      for(ptr1=list1,ptr=list; ptr.next!=null; ptr=ptr.next, ptr1=ptr1.next)
         ptr1.next = new Cell(ptr.next.first*n,null);
      return list1;
     }
}

Many people gave answers to part b) of question 3) which did not involve new cell creation, so could not have constructed an entire new list as required. In some cases, their code would still have had the effect of changing the original list destructively. Quite a few people assumed a new cell could be constructed by new Cell(). This is not the case, because the code for Cell in question 2) gives only a two-argument constructor. A zero-argument constructor for a class is provided automatically only if no other constructor for the class is given. Otherwise, if you want a zero-argument constructor along with other constructors, it will only exist if you write it as part of the class.

An alternative way of tackling this problem iteratively is to go through the original list and put the new cells you are creating at the front of a new list. This will have the result of creating the list you want in reverse order. So you then need to go through this new list again putting the cells on the front of another list, and returning that list as the result. Here is some code which does it this way:

static Cell mult(int n,Cell list)
{
 Cell ptr,temp=null;
 for(ptr=list; ptr!=null; ptr=ptr.next)
    temp = new Cell(ptr.first*n,temp);
 Cell list2=null;
 while(temp!=null)
    {
     ptr=temp.next;
     temp.next=list2;
     list2=temp;
     temp=ptr;
    }
 return list2;
}

A few people answered question 3) by writing code that dealt with arrays of integers. Given the amount of time given in this course to linked lists, it was incredible to see students who did not realise they are an entirely separate thing from arrays. It was particularly strange given that question 3) referred directly to question 2), which clearly was not about arrays.

Question 4

One point to note about questions involving definitions and explanations is that you have to be very precise with them. Computer Science is a precise subject, and you should be careful to use language in such a way as to make clear what you intend and to avoid waffle. Rememer, you can lose marks by adding extra irrelevant waffle, since that detracts from the brief explanation you were asked to give. If you write something that is correct, but then spoil it by adding extra material that suggests you didn't really understand what you wrote, you will lose marks.

In part a), "aliasing" refers to the way two different variable names can refer to the same object. A number of people in answering this question confused "variable" with "object" - in Java it is easy to slip into saying "object" when you mean "variable which refers to an object", but that's a particularly wrong thing to do here when the difference between the two is crucial. Another mistake made more than once was to explain aliasing correctly, but then to spoil it by giving an example involving two variables of type int, which cannot be aliases because they hold primitive values rather than object references. Some people also said that because b=a caused b to be an alias of a then b=c would cause a to change. No - it causes b to stop being an alias for a and start being an alias for c. Aliasing has the effect of appearing to change the object one variable refers to when changing another object (actually the same object under an alias) only when a destructive method is called on one of the variables that refer to that object, or when one of it fields is changed through an assignment. So, after b=a, the code b.field=x will also change what a refers to, as will b.meth(x) if meth is destructive, but making b itself refer to another object won't change a.

Many people answered part b), which asked for an explanation of "tail recursion" just by saying what recursion is. A recursive call is tail recursive if its result is returned directly as the result of the call that made it, or in the case of a void-returning method if it is the last statement that is executed in the method. To answer this question correctly, you had to make quite clear that you understood under what condition a recursive call is tail recursive. Some people wrote answers that looked as if they might understand but used language in such a vague way that it wasn't clear. Quite a few people answered this question in a way that suggested they thought "tail" here referred to the tail of a list, which it doesn't.

Part c) asked for an explanation of "O(N²)". What was required here was something that showed you understood the big-O notation. Many people just said it was "a description of selection sort" or similar words. Although selection sort is O(N²), it is not the only algorithm that is. It was not necessary, or even particularly desirable, to mention selection sort in order to answer this question. Any algorithm is O(N²) if the time it takes to execute is roughly proportional to the square of the amount of data, N, for large values of N. It is not the case, as many people wrote that, O(N²) means an "inefficient algorithm". It all depends on the problem. An O(N²) sort algorithm is inefficient because we know there are better sort algorithms, but there are other problems where an O(N²) algorithm would be very efficient. Some people in answering this question wrote of "selection search" or something similar which suggested they were unaware of the difference between sorting and searching. Sorting puts a whole collection of data in order, while searching simply finds one particular data item in a collection.

Part d) asked for an explanation of "axioms". These are rules which define how a particular data type works. It was important in answering this question that you showed you understood axioms are actually part of the definition of an abstract data type. If you wrote something like just "they are rules a programmer must keep to", that is far too vague.

Question 5

In part a) of this question, you were asked to describe informally how selection sort works. You could have written "You find the lowest item in a collection and put it in the first position of the collection and put the value that was there in the original position of the second item. Then you find the lowest item of all the collection except for the first item and put it in the second position and put the item that was there in the second lowest items' original position. Then you find the lowest item of all the collection except for the first two items and swap it with the itemin the third position, and so on". It was not really necessary to give details of actual variables used in writing the code to do this. However, it was necessary to write the explanation in such a way that anyone who wasn't familiar with selection sort would after reading it understand how it worked. Many people gave answers where this wouldn't be the case.

Part b) of this question asked for an explanation of how you would delete a number from a linked list of numbers. The important thing here was that you had to show clearly that you understood you had to get a pointer to point to the cell before the one being deleted from the list and then alter that cell's next field to refer to the cell the next field from the cell being deleted referred to. Quite a lot of answers didn't show clearly that this was understood.