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

Class: Prepare your answers before the tute!

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

1. 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.
   
   
2. Re [Lists], `reduce' performs the cumulative operation derived from a binary function, f, and a zero, z:

   append:

   append nil L = L

   append (cons h t) L = cons h (append t L)

   reduce:

   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

   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.
   
   
3. 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.)
   
   
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).
   
   
5. 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.