Tute 1, CSE2304, CSSE, Monash, .au, Semester 1, 2002

Group A: week 2, 11-15 March,
Group B: week 3, 18-22 March

Class: Prepare your answers before the tute!

Tutors: (i) The purpose of the tutorials is not to solve the prac's! (ii) The purpose of the tutorials is to check answers, and to discuss particular sticking points, not to simply make answers available. It will only be possible to cover all questions if the class has prepared them all in advance.

1. Give the truth-table for `=>' (implies).
   
   
2. Give the truth-table for   (p => q) => (not p => not q)
   
   
3. An action, not a question: Recap the properties of the Abstract Data Type (ADT) [.../tildeAlgDS/List/].
   Note the fact that most programming languages, and particularly Lisp, use the noun `nil' for the special list-terminating pointer value, and use the adjective `null' for the predicate `equals nil', but C has to be different, of course!
   
   
4. Here are definitions of functions `append' and `sum' in mathematics:

   append:

   append nil L2 = L2

   append (cons h t) L2 = cons h (append t L2)

   sum:

   sum nil = 0

   sum (cons h t) = h + (sum t)

   Prove formally that   sum (append L1 L2) = (sum L1) + (sum L2)   for all lists of numbers, L1 and L2.
   
   
5. A is an array of N integers. An interval, A[i..j], consists of the elements A[i], A[i+1], ..., A[j], if i<=j, and is empty otherwise.
   Give C-code for an efficient algorithm to find the longest interval that contains at most `m' negative elements.
   (There is a linear-time algorithm for this problem.)
   
   
6. Give a logical argument as to why your solution to the previous problem (i) terminates and (ii) is correct.