Tute 1, CSE2304, CSSE, Monash, Semester 1, 2004
Weeks 2 and 3, 8 to 19 March 2004
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.)
(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.
- Give the truth-table for `=>' (implies).
- Give the truth table for (p & (p=>q)) => q.
- Revise the properties of the Abstract Data Type (ADT)
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)
Prove formally that
r (r T) = T, for all trees T.
- 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
sum(r T) = sum T, for all trees T.
- 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, 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 |
|| 3.0 4.0 6.0 5.0 4.0 3.0 4.0 |
- Give a logical argument why your solution to the previous question
(i) terminates and (ii) is correct.
© L. Allison 2004,
School of Computer Science and Software Engineering,
Monash University, Australia 3800.
Created with "vi (Linux & Solaris)", charset=iso-8859-1