Tute 3, CSE2304, CSSE, Monash, Semester 1, 2002
Group A: week 6, 15 - 18 April (19th -> 26th),
Group B: week 8, 29 April - 3 May
Prepare your answers before the tute!
(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.
It will only be possible to cover all questions if the
class has prepared them all in advance.
- 1996 was a leap year because it was divisible by 4,
but 1900 was not because it was also divisible by 100,
although 2000 was because it was also divisible by 400.
Give as short as possible a piece of code to determine if
`year' is a leap year.
- Re [Lists],
`reduce' performs the cumulative operation derived from
a binary function, f, and a zero, z:
If g (g x y) z = g x (g y z), for all x, y and z,
and g z w = w, for all w,
prove formally that
g (reduce g z L1) (reduce g z L2) = reduce g z (append L1 L2),
for all lists L1 and L2.
- append nil L = L
- append (cons h t) L = cons h (append t L)
- reduce f z nil = z
- reduce f z (cons h t) = f h (reduce f z t)
- e.g. reduce plus 0 [1,2,3,4] = 10;
and reduce times 1 [1,2,3,4] = 24
- In an unrooted tree of degree three, each internal node
is connected to exactly three other nodes, and
each leaf is connected to one other node.
How many such trees are there with `n' leaves? Why?
(e.g. the answer is 3 if n=4.)
- Given a binary search tree, T, holding numbers
and a number, k, give code to
find the element in T that is equal to k or,
failing that, is as close to k in value as possible
(resolve ties arbitrarily).
- You are designing some software for analyzing questionnaires.
Each questionnaire has up to 15 questions.
Each question has two possible responses, "a" or "b", or
it can be left blank, "don't care".
The questionnaires and given to a very large group of people
and you must write some code to discover
if the responses of two people match.
Reponse "a" matches "a", response "b" matches "b", and
"don't care" matches anything, "a", "b" and "don't care".
Two people match if all of their responses match.
Devise a representation for the data and give code
that is as fast as possible to determine if
the responses of two people match.
© L. Allison 2002,
School of Computer Science and Software Engineering,
Monash University, Australia 3800.
Created with "vi (Linux & IRIX)", charset=iso-8859-1