[CSE2304] [progress] >>>[ans 4-5]>>>

### Tutorial #1, 2000

1. You should know the answers to these from 1st year, e.g.
``` => F  T  Q   -- P=>Q
F  T  T
T  F  T
P
```
2. Recap the properties of the Abstract Data Type (ADT) [..../tildeAlgDS/List/].
This is an instruction not a question.

3. Use induction on |L|:

(a) map (f o g) nil = nil = map f nil = map f (map g nil) = (map f)o(map g) nil

(b) 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)

4. ```-- 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
end_if;
end_if;
end_for
-- assert: a[first..last] is the longest non-decreasing
-- run in a[1..i-1] and i=N+1, hence desired outcome.
```
5. (i) i must reach N
(ii) See invariant and assertion.
Extra question: if there are two or more equally long maximal runs, which one does the algorithm detect and return?
 © L.Allison 2000 Comp Sci Monash Australia

### Tutorial #2, 2000

1. Hard to beat `small=x<y?x:y' for size.

2. ```  if x < y then
if x < z then -- x < y and x < z
small := x
else -- z <= x < y
small := z
end_if
else -- y <= x
if z < y then -- z < y <= x
small := z
else --  y <= z and y <= x
small := y
end_if
end_if
```
This particular code always carries out two comparisons.

3. a[0..N-1] is an array of integers.
1. ```   min := a;
for i from 2 to N do
-- INV: 1<=j<i => min<=a[j]
if a[i] < min then
min := a[i]
end_if
end_for
-- assert: (1<=j<i => min<=a[j]) and i=N+1
-- so: 1<=j<=N => min<=a[j]
```
Note, we leave out, as "obvious", that min is in a[1..i-1], but if we were being "picky" we would include this too.
2. The remaining options are left to the reader.

1. 100
2. 55
3. 55
4. 40

4. e.g. input = 2 4 6 3 7 5 1
1. find longest decreasing tail: 2 4 6 3 [7 5 1]
2. find the smallest number (5) in the tail which is larger than the number just before the tail (3)
3. swap them: 2 4 6 5 [7 3 1]
4. reverse the tail: 2 4 6 5 [1 3 7]
You should be able to turn this into C code.

### Tutorial #3, 2000

1. 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 = 0 = 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)

2. 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.

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

4. -

5. The following answers one of the two options. Which one?!
```
find(x, T, current)
if T is empty then
return current
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
return element(T)
end_if

initial call:
find(k, T, infinity)  -- e.g. can use maxint for infinity over ints
```

© 2000, L. Allison, Comp. Sci. & SWE, Monash University, Australia