Tute 1, CSE2304, CSSE, Monash, Semester 1, 2003

10 March to 21 March 2003

Class: Prepare your answers to the equestions 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 not be possible to cover all questions if the class has not prepared them all in advance.

1. Which of the following are valid (always true, prove it), or not (state why):
   • p and q => p
   • p or q => p
   • p => p and q
   • p => p or q
   • p and q => p or q
   • p or q => p and q
   • (p => q) => (not p => not q)
   • (p => q) => (not q => not p)
2. An action not a question: Revise the properties of the Abstract Data Types (ADTs) [.../tildeAlgDS/List/] and [.../tildeAlgDS/Tree/]. 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!

3. Given these definitions of append and foldl (fold left),

   append nil ys = ys

   append (cons x xs) ys = cons x (append xs ys)

   foldl f z nil = z

   foldl f z (cons x xs) = foldl f (f z x) xs

   for all elements x, z, and lists xs and ys.

   What do the following do? Give examples.

   foldl (and) true

   foldl (or) false

   foldl (+) 0

   Formally prove that if f(a (f b c)) = f(f a b) c, for all a, b, c, and if f z x = f x z = x (i.e. z is a zero for f), for all x, then

   foldl f w (append xs ys) = f (foldl f w xs) (foldl f z ys),

       for all w, lists xs and ys, and functions f.

4. Solve the ``find the second-largest distinct value in an array'' problem from the programming- [Question-List (click)].
   Give a logical argument as to why your algorithm (i) terminates and (ii) is correct.