Tutorial #1, 2000
- You should know the answers to these from 1st year, e.g.
=> F T Q -- P=>Q
F T T
T F T
- Recap the properties of the Abstract Data Type (ADT)
This is an instruction not a question.
- Use induction on |L|:
map (f o g) nil =
map f nil =
map f (map g nil) =
(map f)o(map g) nil
map (f o g) (cons h t) =
cons ((f o g) h) (map (f o g) t) =
cons ((f o g) h) ((map f)o(map g) t) =
cons (f (g h)) (map f (map g t) =
map f (cons (g h) (map g t)) =
map f (map g (cons h t)) =
((map f)o(map g))(cons h t)
-- PRE: N >= 1
first := 1; last := 1; startRun := 1;
for i from 2 to N do
-- INV: a[first..last] the longest nondec' run in a[1..i-1]
-- and a[startRun..i-1] is non decreasing
if a[i] < a[i-1] then -- end of last run
startRun := i;
else -- a[i] >= a[i-1]
if i-startRun > last-start then -- breaks record
first := startRun; last := i
-- assert: a[first..last] is the longest non-decreasing
-- run in a[1..i-1] and i=N+1, hence desired outcome.
- (i) i must reach N
(ii) See invariant and assertion.
if there are two or more equally long maximal runs,
which one does the algorithm detect and return?
Tutorial #2, 2000
- Hard to beat `small=x<y?x:y' for size.
if x < y then
if x < z then -- x < y and x < z
small := x
else -- z <= x < y
small := z
else -- y <= x
if z < y then -- z < y <= x
small := z
else -- y <= z and y <= x
small := y
This particular code always carries out two comparisons.
- a[0..N-1] is an array of integers.
min := a;
for i from 2 to N do
-- INV: 1<=j<i => min<=a[j]
if a[i] < min then
min := a[i]
-- assert: (1<=j<i => min<=a[j]) and i=N+1
-- so: 1<=j<=N => min<=a[j]
we leave out, as "obvious", that min is in a[1..i-1],
but if we were being "picky" we would include this too.
- The remaining options are left to the reader.
- e.g. input = 2 4 6 3 7 5 1
You should be able to turn this into C code.
- find longest decreasing tail: 2 4 6 3 [7 5 1]
- find the smallest number (5) in the tail which is
larger than the number just before the tail (3)
- swap them: 2 4 6 5 [7 3 1]
- reverse the tail: 2 4 6 5 [1 3 7]
Tutorial #3, 2000
- Use induction on the length of lists or size of trees:
- (a) length (append nil L2) =
length L2 =
0 + length L2 =
length nil + length L2
(b) length( append (cons h t) L2) =
length( cons h (append t L2) ) =
1 + length(append t L2) =
1 + length t + length L2 =
length(cons h t) + length L2
- (a) weight empty_tree =
length nil =
length( flatten empty_tree )
(b) length(flatten( fork e L R )) =
length( append((flatten L) (cons e (flatten R)))) =
length(flatten L) + length(cons e (flatten R)) =
weight L + 1 + weight R =
weight(fork e L R)
- This is a sketch, not a complete answer:
0 0 0 0 1 1 1 ? ? ? ? ? ? 2 2 4 4 4 4 4 4
^ ^ ^ ^
| | | |
p q r s
a) Invent a suitable invariant describing the 5 sections of the array,
possibly empty, 4 coloured, and one unknown but shrinking.
b) In a loop, examine a[q] (or a[r]),
manipulate the pointers and possibly move some element(s),
to maintain the invariant, while . . .
c) . . . making sure that q and r get closer and closer.
- Time-complexity as per 3-colour flag problem
and you surely remember what that is.
(The "constant" is a little worse.)
Extra question: So if we consider 5 colours, 6 colours, ...,
N-colours, why can't we sort in better than
O(n.log(n))-time in general?
- The following answers one of the two options. Which one?!
find(x, T, current)
if T is empty then
elsif element(T) < x then
return find(x, right(T), current)
elsif element(T) > x then
return find(x, left(T), min(element(T), current))
else -- equal
find(k, T, infinity) -- e.g. can use maxint for infinity over ints
© 2000, L. Allison, Comp. Sci. & SWE,
Monash University, Australia