CSE2304 Tutorial #3 semester 1, 2000

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.
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.
What is its time-complexity?
How many different shapes of binary search trees are there for each of the following numbers of elements:
1, 2, 3, and 4.
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.