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.

1. Given array a[] of size n, and ints i and j write the shortest possible piece of C-code, that runs in O(n)-time, to swap a[0..i] with a[j+1..n-1], 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

   
   
2. Given an array a[] of numbers (positive and/or negative), write C-code to find i and j, such that (i) j>=i-1 and (ii) the sum a[i]+a[i+1]+...+a[j] is as large as possible. (There is a linear-time algorithm.)
   
   

3. 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?

   
   

4. We gave the slow (fs) and fast (ff) tree-flattening 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.