Tutorial 1, CSE2304, Monash, Semester 1, 2006

Week 3, begins 13 March

Class: The tutorials are the primary vehicle for practising the more formal material of the unit. Prepare your answers to the questions before the tutorial! It will probably not be possible to cover all questions unless you have prepared them in advance. Note that the online versions of the tutorials, as available at the unit's home page, are the reference documents and 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, the specification and analysis of algorithms and data-structures, and mathematics and logic useful in the above.
This tutorial also includes revision of some mathematics from the unit's prerequisites.

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)

    

   Note, the value-constructor Fork has three parameters, but in maths and several programming languages, we can write Fork p1 p2 p3, rather than the longer Fork(p1, p2, p3). Fork is said to be [curried].

    

   You have to prove some properties of the algorithms and trees:

   (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.

   These are much stronger results than mere testing can provide. An optimising compiler could safely use this kind of property to improve the time-complexity of programs.

   
   

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 (an exact formula if possible else approximate) for the 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	7	...	answer
      							...	?

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