Tutorial 1, CSE2304, CSSE, Monash, Semester 1, 2005

Weeks 2 & 3,  7 to 18 March

Class: Prepare your answers to the questions before the tutorial! It will probably not be possible to cover all questions unless the class has prepared them all in advance. (The online versions of the tutorials may contain extra information and links.)
Tutors: (i) The purpose of the tutorials is not to solve the practical exercises! (ii) The purpose is to check answers, and to discuss particular sticking points, not to simply make answers available.

Objectives: The tutorials give practice in problem solving, in analysis of algorithms and data-structures, and in mathematics and logic useful in the above.

1. Which of the following are valid (always true, prove it), or not (state why, give a counter-example):
   1. p and q => p
   2. p or q => p
   3. p => p and q
   4. p => p or q
   5. p and q => p or q
   6. p or q => p and q
   7. (p => q) => (not p => not q)
   8. (p => q) => (not q => not p)
   
   

2. Here is one possible abstract data type for a binary-tree data-structure having an arbitrary element type, e:

   Tree e = EmptyTree | Fork e (Tree e) (Tree e)

   Here are definitions of two algorithms, m on all trees and sum on trees of numbers:

   m EmptyTree = EmptyTree

   m (Fork e lf rt) = Fork e (m rt) (m lf)

    

   sum EmptyTree = 0

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

    

   You have to prove some properties of the algorithms:

   (i)  Prove formally that  m (m T) = T, for every tree T.

   (ii) Prove formally that  sum(m T) = sum T, for every tree T.

   
   

3. Here is a problem to solve: A[] is an array of N floating point numbers; N might be very large indeed. A[] contains some volatile time-series data. We want to "smooth" the data.

   (i) 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 2.0 5.0 -> 3.0,   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

   (ii) Give a logical argument why your solution to part (i), (a) terminates and (b) is correct.
   

   
   
4. Each part of this question gives the first few elements of an infinite series of diagrams for n = 1, 2, 3, ... .
   For each series, give a formula for the (exact if possible else approximate) number of rectangles in the n^th diagram of that series.

   e.g.	1 2 3 4 ... answer ... 2×n

   1. 1	2	3	4	5	...	answer
      					...	?

   2. 1	2	3	...	answer
      			...	?

   3. 1	2	3	4	5	6	...	answer
      						...	?

   4. 1	2	3	4	...	answer
      				...	?