[CSE2304] [progress]

### CSSE, Monash University, .au, CSE2304, Tutorial #3, semester 1, 2001 Group B: week 6, 2 April... Group A: week 7, 9 April... (NB. Friday -> 27th)

Class: Prepare answers before the tute; it will not be possible to cover all the questions unless you do.

1. Re [Lists], here are the definitions of `map' which applies a function to every element of a list, and of `reduce' which performs the cumulative operation derived from a binary function, g, with a zero or identity value, z:
• map f nil = nil
• map f (cons h t) = cons (f h) (map f t)
• e.g. map square [1, 2, 3] = [1, 4, 9]
• reduce g z nil = z
• reduce g z (cons h t) = g h (reduce g z t)
• e.g. reduce multiply 1 [1, 2, 3, 4] = 24
Prove formally that   not (reduce and true L) = reduce or false (map not L)   for any list, L, of Boolean (truth) values.

2. Here is a rough idea for a sorting algorithm:
Move all the even elements, if any, to one end of the array and move all the odd elements, if any, to the other end of the array. Somehow[*], sort all the even elements and sort all the odd elements.
Design an algorithm from this idea and state its time and space complexity.
[*] Note that even/odd involves testing the least significant bit. What about the next bit?

3. How many different shapes of binary search tree are there that contain exactly 5 elements.

4. Give code or an algorithm for the following problem:
For a binary search tree, `T', and a range, `lo' to `hi', print all elements, if any, in the tree whose values are between `lo' and `hi' inclusive.

© 2001, L. Allison, Comp. Sci. & SWE, Monash University, Australia