Tute 1, CSE2304, CSSE, Monash, Semester 1, 2004

Weeks 2 and 3, 8 to 19 March 2004

Class: Prepare your answers to the questions before the tute! It will probably not be possible to cover all questions unless the class has prepared them all in advance. (The online versions of the tutes may contain extra information and links.)

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.

1. Give the truth-table for `=>' (implies).

2. Give the truth table for   (p & (p=>q)) => q.

3. Revise the properties of the Abstract Data Type (ADT) [.../tildeAlgDS/List/]. Note the fact that most programming languages, and particularly Lisp, use `nil' for the name of the empty list (i.e. the special list-terminating pointer value), and use the adjective `null' for the predicate `equals nil', but C has to be different, of course!
   Revise the properties of the Abstract Data Type (ADT) [.../tildeAlgDS/Tree/].
   
   

   1. Here is one possible definition of a binary tree ADT:

      Tree e = Empty | Fork e (Tree e) (Tree e)

      Here are a couple of functions on trees:

      r Empty = Empty

      r (Fork e lf rt) = Fork e (r rt) (r lf)

      sum Empty = 0

      sum (Fork e lf rt) = e + (sum lf) + (sum rt)

      Prove formally that   r (r T) = T, for all trees T.
      
      
   2. Prove formally that   sum(r T) = sum T, for all trees T.

4. A[] is an array of N floating point numbers; N might be very large indeed. A[] contains some volatile time-series data. Write efficient C-code to print a "smoothed" version of the data in A[], smoothing over a sliding "window" of width w, where w is an odd, positive integer, possibly very large. E.g. if w=3,   2.0 5.0 5.0 --> 4.0,   5.0 5.0 8.0 --> 6.0,   etc.. To deal with the ends of A[], pretend that it is extended to the left with copies of A[0], and is extended to the right with copies of A[N-1], e.g.

   w=3, A[]=	2.0 5.0 5.0 8.0 2.0 2.0 5.0
   smoothed:	3.0 4.0 6.0 5.0 4.0 3.0 4.0

5. Give a logical argument why your solution to the previous question (i) terminates and (ii) is correct.