CSE2304 Tutorial #3 semester 1, 2001

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

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.
Here is a rough idea for a sorting algorithm:
Moveall 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.
Designan 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?
How many different shapes of binary search tree are there that contain exactly 5 elements.
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.