[CSE2304] [progress]

CSE2304, Tutorial #3, semester 1, 2000
Group A: week 6, 3 April...
Group B: week 7, 10 April...

  1. For [Lists] and [Trees], Prove formally that length(append L1 L2) = length L1 + length L2, for any pair of lists L1 and L2.
    And for more of a challenge: Prove formally that length(flatten T) = weight T, for any tree T.

  2. Give an algorithm (or code) for the 4-colour [flag problem]. i.e. if colour(e) returns one of the colours 1, 2, 3 or 4, for an element e. Rearrange the array A[ ] so that of all of the colour#1 elements precede all of the colour#2 elements which precede all of the colour#3 elements which precede all of the colour#4 elements.
  3. What is its time-complexity?

  4. How many different shapes of binary search trees are there for each of the following numbers of elements:
    1, 2, 3, and 4.

  5. Give code / an algorithm for the following problem:
    For a binary search tree, `T', and a query, `k',

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