^CSE2304^
Tute 3, CSE2304, CSSE, Monash, Semester 1, 2003
7 to 11 April and 28 April to 2 May 2003
Class:
Prepare your answers to the questions before the tute!
Tutors:
(i) The purpose of the tutorials is not to solve the prac's!
(ii) The purpose of the tutorials is to check answers, and
to discuss particular sticking points, not to simply make answers available.
It will not be possible to cover all questions if the
class has not prepared them all in advance.

 Given array a[] of size n, and
ints i and j
write the shortest possible piece of Ccode,
that runs in O(n)time,
to swap a[0..i] with a[j+1..n1],
e.g.
 before a[] = 0 10 20 30 40 50 60 70 80 90 100 110,
i=2, j=6
 after a[] = 70 80 90 100 110 30 40 50 60 0 10 20
 Given an array a[] of numbers (positive and/or negative),
write Ccode to find i and j,
such that (i) j>=i1
and (ii) the sum a[i]+a[i+1]+...+a[j]
is as large as possible.
(There is a lineartime algorithm.)

 How many different shapes of binary search trees are there
for each of the following numbers of elements:
 0, 1, 2, 3, and 4
 Is there a pattern? If so what?

 We gave the slow (fs) and fast (ff)
treeflattening algorithms in an early lecture:
 fs emptyTree = nil
 fs (fork e l r) = append (fs l) (cons e (fs r))
 append nil l = l
 append (cons h t) l = cons h (append t l)
 and
 ff tr = f tr nil
 f emptyTree ans = ans
 f (fork e l r) ans = f l (cons e (f r ans))
 formally prove that
 fs t = ff t, for all trees t.
© L. Allison 2003,
School of Computer Science and Software Engineering,
Monash University, Australia 3800.
Created with "vi (Linux & Solaris)", charset=iso88591