====================================================================== Faculty of Applied Science and Engineering, University of Toronto CSC181: Introduction to Computer Programming, Fall 2000 Final Exam Marking Scheme ====================================================================== ---------- Question 0 ---------- Scheme: * (-1/-2): Student number not written on every page. * (-2): Part (b) not attempted. * (-2): Part (c) not attempted. Comments: * Note the word "attempted" for parts (b) and (c). I didn't care whether you got these wrong or right, as long as you tried to answer them. There seem to be differing opinions as to what are the right answers for (b) and (c). I thought I used checkmarks and crosses, but some of you said I circled things. Maybe. I honestly don't know. ----------- Question 1a ----------- Scheme: * (-1): Does not check 'elements' * (-1): Iteration not based on 'size' * (-1): Off-by-one error * (-2): Does not return correct value * (specified): Other error Comments: * Generally well done. ----------- Question 1b ----------- Scheme: * (1): Addresses array overflow with assertion/comment * (1): Checks whether element is in set * (2): First loop to look for position * (3): Second loop to shuffle elements over * (2): Inserts element into correct spot * (1): Increases 'size' * (specified): Other error Comments: * Generally well done. ----------- Question 1c ----------- Scheme: * (-8): Always uses 'add' to add elements * (-4): Uses 'add' to add elements in special cases * (-2): Uses 'retrieve' to determine size of set * (-4): Forgets to add elements (once finished processing one array) * (-4): Does not handle duplicate elements * (-2): Does not address array overflow with comment * (specified): Other error Comments: * Not done very well. * Repeated adding of elements through 'add' is not efficient in time, since it involves repeated insertions into a sorted array. Ideally, you should use a modified version of the merge algorithm, which is way more efficient in time. (That's why the hint was there!) ----------- Question 1d ----------- Scheme: * (5): Base case * (10): Recursive case * (specified): Other error Comments: * Generally well done. In the future, see if you can eliminate if-else branches which are ultimately redundant (that is, on if-else branch tests a condition that is tested by another branch). ----------- Question 2a ----------- Scheme: * (1): Loop initialization * (1): Loop increment * (3): Loop test/condition * (1): Return type * (3): Returns first character which isn't c * (1): Returns null if array contains only c's * (specified): Other error Comments: * Generally well done. ----------- Question 2b ----------- Scheme: * (-2): Memory allocation improperly/not done * (-1): Fixed-size array used * (-2): Returned pointer from 'nextToken' points to local variable * (-1): Null character not appended to returned token * (-2): Advances to next token when 'hasMoreTokens' is called * (-2): Does not find token boundaries correctly * (specified): Other error Comments: * Generally well done. * The first three errors were most common, reflecting discomfort with or misunderstanding of memory management issues. You will deal with memory management issues again in future programming courses, so if you had problems with these, keep trying to understand them better. ---------- Question 3 ---------- Scheme: * (3): Choosing the right move * (2): Drawing the correct boards at level 1 * (4): Calculating the correct values (maximums) at level 1 * (8): Drawing the correct boards at level 2 * (8): Calculating values at level 2 Comments: * Generally well done. * Note that it says you just had to calculate values at level 2. If you missed a couple of values, you didn't lose any marks. What was more important was that you demonstrated that you understood that the boards had to be evaluated, and that the appropriate maxima would need to be calculated. * Some people calculated the minima of the evaluations for level 2, but that wouldn't make sense given the evaluation function (which is positive for scores favourable to X--the max). ------------------ Question 4a and 4b ------------------ Scheme: * (6): Outer loop/function for selection sort * (9): Inner loop/function for bringing minimum to front * (5): Swap code fragment * (-1): Off-by-one error * (-1): Uses static variables * (-1): Inefficient * (specified): Other * These functions were done with varying degrees of success. * For the linked sort, many people attempted to (and most succeeded at) manipulate the links of the list during each swap. This wasn't necessary, as you can just swap only the data of the nodes without having to touch any links. * Some people wrote the array sort by starting from the end (the maximum) rather than the beginning. This was fine, and in some cases, led to shorter (correct) code.