CSC148H  SUMMER 96

COMMENTS ON THE DAY SECTION MIDTERM
-----------------------------------

The average was 63%.  You can look up your grades on the web page.

Question 1:
-----------

a. INCORRECT reasons why it is still necessary to test a program even after
proving it correct:
	- proof may be wrong or may not handle all cases
	- need to test boundary cases
	- need to test different combinations of input
	- proof only proves algorithm, not program

b.  - Many people did not realize that if you have a pointer to an element 
      of a list, you don't need to follow the links from the beginning of the
      list to find it again.  
    - The complexity of the "process" that finds the pointer to the element
      to be deleted should not be counted when determining the complexity of 
      the delete procedure.  (Only because of the way the question was put.)
    - The answer "It is still O(n) because O(1) is O(n)" was not accepted.
    - The correct answer was that the procedure remained O(n) because we also 
      need a pointer to the element in front of the one we want to delete, and
      finding that element takes O(n) time.

c) Almost everyone got this question.


Question 2:
-----------

a. 
   - Many students put a precondition that should appear in (b) here.
   - Some just said "list3 contains elements of both list1 and list2".
   - Some just mentioned insignificant postconditions like 
       "i > upper(list1)", "list1 and list2 are unchanged", ...

b. - As said in (a), the precondition is misplaced in some answers.
     The precondition is:
        2*upper(list2) = 2*upper(list1) = upper(list3)   OR

        upper(list1) <= upper(list2) and 2*upper(list1) <= upper(list3)

   - Some put "i=1" as the only precondition.

c. Nearly everyone got this.

d. Some answered "NO" because they thought that the statement is false when
   i=1.  (For i=1 in 1<=k<=(i-1), there are no values of k, so the
   statement list3(2k-1)=list1(k) is true.) 

e. A well-answered one.


Question 3:
-----------

a. Most people got it correct, even if the reasoning was a bit
   strange:  O(n^2).

b. Many people thought random2 was also O(n^2) because they thought one call
   to randint took n/2 operations, when really it is constant time.  (In
   random1 we make n/2 CALLS to randint on average.)

c. Well answered.  The major error was in misreading the
   question to ask "Which procedure is more efficient?"

d. There are many acceptable answers:
	- infinite
	- unknown
	- can't say
	- can't say in terms of n
        - O(n*m), where m is the maximum number of calls to randint
          required to get a specified number.
   Many people guessed.  Some said it would still be O(n^2) because
   they thought it would take n calls at most to randint to get a
   specified number (which wrong, since it can repeat numbers).

As a side note, this is very similar to what was required on A2 to
generate the random cipher.  Some people even wrote O(n^3) programs.
If you didn't think of the fast program, now you see that you can
generate the random cipher by choosing exactly 26 random numbers.


Question 4:
-----------

The answers are:  5, 15, 50, -90, error

 - Some did not understand at all. (time pressure?) 
 - Some would pop none or only one element although there was the
   pop()+/-pop() command executed.
 - Some did some subtraction errors.
 - Some failed to see the error at the last question
 - Some didn't understand what push(S, pop(S) + pop(S)) could possibly
   mean.  It is the same as the following, only shorter and more
   efficient:
       var a : int
       var b : int
       a := pop(S)
       b := pop(S)
       push(S, a+b)

Drawing a stack and showing what is happening for a single add() or
subtract() call helps.