ADS2 May 2016 Feedback Exam Paper ---------- Q1. Write java code for stack. Many students had an if statement to detect and throw an exception on underflow/overflow and then had an "else" statement after that. This suggests a lack of understanding of java. Part (b) was to identify advantages and disadvantages of the dynamic data structure, in particular no overflow but need for garbage collection. Many said disadvantage was O(n) cost of finding and deleting an object in a linked list. But it is a stack so you only ever add and delete from the head. This showed a basic failure to understand how a stack works and "writing everything I know about linked lists" rather than answering the question. Part (c) was covered in class twice, once using fridge magnets and expressive dance. Again, reading the question it says "... explain how the enqueue and dequeue operations would be realised, ...". Rarely did a student describe enqueue and then describe dequeue. Instead, students wrote everything they know about stacks and queues. By the way, 1(b), you can do enqueue in O(1) and dequeue in O(1). Q2. All to do with open and closed hashing. We had lectures on this and two beautiful demos on our website. Part (e), very few actually explained why we need to record removals and how this can then be exploited when adding to the table. Q3. Very few students explained how worst case comes about. They might say "bad pivot" or "sorted data", when in fact it is a combination of these, when pivot selects largest or smallest item and degenerates to selection sort. Again, we had a lovely demo of this in the lectures and on the web. Some students described the wrong algorithm and some said parts were merged together (they are joined or appended, no merge takes place, and if it did it would up the complexity). Q4. In lectures we covered something like this, demoed a cellular automata, and discussed algorithms and data structures for this. This was also touched on in revision lecture. The inner loop is in fact O(1) so overall complexity is O(n.n) i.e. quadratic in n. Q5. This was pure recall and was easy and marks were as expected. Most students failed to mention recursive nature of the tree structure, and didn't mention basic properties of a tree. Part (b), hardly any student gave an actual simple example (insert 1,2,3; compare with insert 2,1,3 and talk about hieght and effect on search). Tendency was to write a page or more of text. AVL tree, most didn't mention recursive nature of the property (see the slides) so was incorrect. Overall ------- Students have a habit of writing as much as they can about a given topic without thinking about and addressing the actual question asked. Generally, there are three kinds of questions. The first and most basic is to test knowledge, i.e. "recall". But this should be focussed recall, not recalling everything you know, but recalling only what is relevant. Questions 2 and 5 are examples of this. Sometimes I think of this as "talking the talk", you actually sound like you know what you are talking about. The second type of question is "comprehension", i.e. you are given something and you have to work with it. Question 1(a), 1(b) and question 4 are examples of this. I think of this as "walking the walk", i.e. you can actually do it. The third kind of question is one that allows a student to show that they can think on their feet, that they can be inventive, that they have insight. You don't want too many questions like this in an exam, but it is nice to have some so that the really excellent student can show that she/he is really excellent. Question 1(c) is an example of this. Most students tried to "walk the walk" on 1(c) and got average marks, a few took off and showed that they can fly. Exam Procedures ----------------- Some students wrote on the left hand pages of the script. The instructions clearly state not to do so and that this material might not be marked (but I always did mark it). Also, some students' writing was nearly illegible (again, see instructions on script). If your examiner cannot read your script, how can they mark it? Hint: make sure that what you write can be read, and write on the right. Assessed Exercises ------------------ We had two, marked by lab group tutors. There was some evidence of plagiarism, but few cases were followed up. Feedback was given to exercises by tutors and in the lectures and in example classes. No model answers were distributed as these tend to propagate to following years' students. Model answers were presented in lectures (along with model mistakes). Patrick Prosser 25/05/2016