[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: 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