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?

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[1];
         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.
   
   
4. 1. 100
   2. 55
   3. 55
   4. 40
   
   
5. 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