csc 148			Midterm Exam
fall 1995		Comments from the Markers
-------------------------------------------------------------------------

Below is a collection of comments from the markers of the midterm exam.
A common theme is mis-reading questions.  The ability to read precise
descriptions or instructions is as important as the ability to write 
precisely.

Remember that solutions to the exam are in the library.


Question 3a
-----------
An appropriate integer value is last-first.

One mark if they give something similar, but that is not an integer 
value eg, first<=last or last-first>=0.

A lot of people put wrong answers like: MID, FIRST, or LAST which do 
NOT decrease on every iteration.  Also note that N does not change in 
the loop so this is also wrong.


Question 3b
-----------
Expected answer: FIRST<=LAST, LAST-FIRST>=0, or something similar.

Answers to 3b were marked relative to what the student gave for 3a.
For example, if they said LAST in Q3a, the statement 1<LAST<N would 
be ok here.


Question 3c
-----------
Expected: prove that LAST-FIRST decreases on any iteration.

Part marks were allocated for the proof.  In particular, we were 
looking for:

   - reference to a "complete" iteration of the loop (does not exit)
   - reference to IF and ELSE conditions inside loop
   - reference to code changing value of LAST or FIRST
   - use of Assumption 2 plus algebra to show that 
	LAST'-FIRST' < LAST-FIRST
   - conclusion statement saying LAST-FIRST decreases on any pass 
     through loop

Notes:
2 marks were deducted if induction was used to prove this 
(it is NOT needed).
2 marks were deducted if TERMINATION was proven (this subsumes the 
proof of LAST-FIRST decreasing on any iteration, but is not what 
was asked for).

There were many problems, mainly due to the fact that people made 
mistakes in Q3a or choose to prove something in Q3b instead of Q3a.  
Rather than giving zero marks for such answers, we gave a small number 
of marks for the solutions:

   - up to 6 marks for an inductive proof of LOOP INVARIANT like Q3b
   - up to 4 marks for a proof of a loop invariant over a single 
	iteration
   - up to 3 marks for proving an incorrect answer 
	(like MID always decreases)


Question 4
----------
	overall it went quite well, however many students
	lost 2 points in part (a) since they claim that it
	was O(1)


Question 5
----------
	(a) - most students gave a correct answer, but a
	couple of students said that it was O(2^n) which
	really puzzled me.

	(b) many students lost marks because they did not 
	make sure (by stating preconditions or making a comment)
	that the queue is not empty.  Others 
	did not decrease the counter by 1

	Also, a lot of students do not read the question
	carefully and they wrote a code for all kinds of things 
	but the LEAVE operation in a circular list. They got
	zero in most cases.


Question 6
----------
	(a) most students did not draw pointers explicitly for
	variables a, b, c, and d, and they lost one mark 
	for that.  Otherwise, how could you know if a is the
	record itself or a pointer to it?

	(b) a lot of students do not know how to check if
	the list is empty. They have all kinds of things:
		front->name = " "
		front->another = nil
		....
	instead of just front = nil
	
	Again, many students did not read the instructions
	and they wrote of kinds of things - adding a new
	record to the list, creating a list, searching 
	a list etc.