Tutorial 1, CSE2304, Monash, Semester 1, 2006
Week 3, begins 13 March
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.
(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.
The tutorials give practice in
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.
Which of the following are valid (always true, prove it),
or not (state why, give a counter-example):
- 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)
- 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
- 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.
- 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, 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
- (ii) Give a logical argument why your solution to
part (i), (a) terminates
and (b) is correct.
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 nth diagram of that series
| 1 || 2 || 3 || 4 || ... || answer |
| 1 || 2 || 3 || 4 || 5 || ... || answer |
| 1 || 2 || 3 || 4 || 5 || 6 || 7 || ... || answer |
Faculty of Information Technology (Clayton),
was School of Computer Science and Software Engineering,
Created with "vi (Linux & Solaris)", charset=iso-8859-1