^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 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
- 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.)
-
- 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)
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.
© L. Allison 2003,
School of Computer Science and Software Engineering,
Monash University, Australia 3800.
Created with "vi (Linux & Solaris)", charset=iso-8859-1