General feedback on Inf1OP Advanced Programming Exam 2015

General comment

I saw lots of code like this:


for (Object i : ys)
   if (i.equals(x))
      return true; // just check if x is an element of ys
return false;

i.e. single-line blocks marked only by indentation, not {}. The fact that this is legal doesn't make it a good idea. Just don't, unless you're putting the whole block on the same line with the conditional, e.g.


if (i.equals(x)) return true; // fine even according to me ;-)

Trust me on this, it's asking for someone else (or even you) to be misled by the indentation and introduce a bug later. (Admittedly, less likely than it used to be, now that most people use syntax aware editors; but still.)

Question 1

This was intended as a light-hearted warm-up, but actually it caused more problems than questions I had thought would be harder!

Most people who tried it got (a) right, though some made "let's throw away marks in the exam" type errors like not implementing a main as requested, or giving the function the wrong name! The point is that doing % 2 on a negative number gives, not 1, but -1. (Note that in base 2, -1 = 1, so if Java were really implementing that, there wouldn't be a difference to be seen - but Java doesn't have a "base 2 integer" type...)

There were two reasonably succinct bodies for isTrulyOdd:


return i % 2 != 0;

and


return Math.abs(i) % 2 == 1;

(actually the abs can be applied either to i or to the entire LHS, and I saw both). Perhaps the former is slightly preferred, as not requiring a call to a library function, and being only two characters different from the given body.

To (b) and (c) I saw only one correct answer (well done Adam!). How could it possibly be that a while loop with condition (i == i + 1) could be executed even once, never mind go on for ever? Note to start with that we are not told the type of i. We can see that it's something on which + makes sense; that could be any numeric type, or String. The name i suggests it's an integer, but it's already clear this is a trick question... As a children's riddle, the question "what number stays the same when you add one to it?" has the fairly obvious answer "infinity", and that gets you on the right track. Type int doesn't have infinity as a value... but type double does have a defined constant Double.POSITIVE_INFINITY, and that's the definition we want.

Having got (b), (c) is fairly easy as it requires the same kind of thinking. How can a loop with condition (i != i) go on for ever? It turns out that Double.NaN ("not a number"), or any expression that evaluates to that, will do fine.

Question 2

Some good solutions to this. Here's one place where you can find full ArrayList code.

Here's my cut-down version to which I'd have given full marks. Note the half-hearted attempt at being something less than horribly inefficient: at least mine doesn't copy the entire backing array on every add or remove...

Many people wrote code where indexOf blindly sent equals to each element of the list in turn, and thus would break if any element were null, although their code did permit null to be entered as an element. I think you do need either to check that you don't permit anyone to add a null element, or else to handle null elements properly. But I didn't penalise it.

In the add method, I several times saw code a bit like this, where myList is an existing array (the old backing array)


int[] temp = new int[size];
temp = myList;

Note that the allocation in the first line is completely pointless! The second line does not do an array copy; it just makes temp be a new reference to the same array that myList is (and its length is whatever the length of myList is, for example - the value of size is irrelevant, though in most people's code it did happen to be the length of myList also). Now the new int[size] created in the first line is garbage collected, as nothing points to it any more... What you wanted was simply


int[] temp = myList;

The real ArrayList has two versions of remove, one taking an index and one taking an Object; I didn't tell you which to implement. Most people did the former, but either was fine.

I saw quite a few bits of code a bit like this:


			int i=0;
			for(String str1 : aList){
				bList[i] = str1;
				i++;
			}

If you want to use the loop variable explicitly, it's better - less error prone - to use a conventional for loop, e.g.

for (int i=0; i <
aList.length; i++)

. Save the foreach loop for where you don't care about the loop variable.

Question 3

Here's my attempt at this.

Note that the best way to do this in Java turns out to be an oft-discussed question. Here is one place to start.

About how the Haskell version works: almost everyone did what I did, on the assumption that in this case the evaluation would be strict and the map would be done before the fold was begun. Then, when one student didn't, I wondered whether Haskell's laziness actually means that that map will be done only as demanded by the foldr... to which the answer seems to be Probably. The Haskell expert I asked commented that "Haskell's cost model is, er, non-trivial." and gave various helpful advices which I haven't followed up yet... maybe you'd like to.

Very few people (including me!) took notice of the fact that this is a foldr not a foldl, and I didn't expect it, but well done those who did. Note that equals is required to be symmetric (ish) so we don't need to worry (much...) about which object we call equals on.

Question 4

Here's an easy way to do this, using a Pattern and an associated Matcher.

(My code assumes, as did most of yours, that the input String is non-null: as so often with null, this is the kind of thing that ought to be specified in a precondition. As I hadn't mentioned it in the question (only in my code!), I gave credit for both ways.)

Many people did it the hard way by building their own, and it's not really that hard if you do it efficiently; that was fine. Here are some tests too.

Thanks to Kerri for starting these off!

Question 5

This was pretty well done by the relatively small number of people who attempted it. Here's one solution. Several of you had solutions involving split(); next time I might make sure that won't work, as I had hoped to make you use the scanner :-)

Question 6

First, I'm sorry about the nonsense I introduced into this. Here's the web page of the exercise from which I adapted this question, which, you see, led readers through it in a way I didn't quite want to.

Perhaps because my error made it so confusing, or perhaps because few people have looked into concurrency much yet, there were very few attempts at this and no really good ones. Consider having a go now!

Do not synchronize the whole run method! You're then removing the concurrency from the program altogether, basically: whichever thread gets to start first gets to do all its counting before the other can start. That was the force of "Take care not to slow the program's execution more than you must.". See this Stackoverflow page for example.

Question 7

Nobody did this; pity! Another time I would definitely try to have a question that got more into OO design. Any other suggestions would still be welcome - as would feedback on whether doing it another year is worthwhile.