[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],
• length nil = 0
• length (cons h t) = 1 + (length t)
• append nil L = L
• append (cons h t) L = cons h (append t L)
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:
• weight empty_tree = 0
• weight (fork e L R) = 1 + (weight L) + (weight R)
• flatten empty_tree = nil
• flatten (fork e L R) = append (flatten L) (cons e (flatten R))
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',
• Group A: find the least element (if any) in T that is greater than or equal to k.
• Group B: find the greatest element (if any) in T that is less than or equal to k.

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