CSE2304, 2003, Semester 1, CSSE, Monash, .au, Tute notes

Notes on some of the tute questions.

Tute 1

• Prove foldl f w (append xs ys) = f (foldl f w xs) (foldl f z ys)

• Base case, xs = nil

  LHS

  = foldl f w (append nil ys)

  = foldl f w ys   -- defn of append

  = f w (foldl f z ys)   -- ???, see below

  = f (foldl f w nil) (foldl f z ys)   -- defn of foldl

  = RHS

   

  ??? foldl f w ys = f w (foldl f z ys) ???

  Note that z is a zero for f.

  Base, ys = nil

  LHS = foldl f w nil = w = f w z = f w (foldl f z nil) = RHS

  General, ys = cons u us

  LHS

  = foldl f w (cons u us)

  = foldl f {f w u} us   -- defn of foldl

  = f {f w u} (foldl f z us)   -- induction on |us|<|ys|

  = f w (f u (foldl f z us))   -- f is associative

  = f w (foldl f u us)   -- induction

  = f w (foldl f z (cons u us))   -- defn of foldl

  back to the main thing...

   

• General case, xs = cons v vs

  LHS

  = foldl f w (append (cons v vs) ys)

  = foldl f w (cons v (append vs ys))   -- defn of append

  = foldl f {f w v} (append vs ys)   -- defn of foldl

  = f (foldl f {f w v} vs) (foldl f z ys)   -- induction on |vs|<|xs|

  = f (foldl f w (cons v vs)) (foldl f z ys)   -- defn of foldl

  = RHS

Tute 2

Q2 Note that M is given. M is fixed for the computation.

Need some data structure, DS, to hold the distinct values in A[i..i+M-1] together with counts of how often each such value appears in A[i..i+M-1]. Update DS as A[i-1] "drops out of", and A[i+M-1] comes into, the interval when i increases.

Implementing DS by an array, sorted by value, is "acceptable" if M is very small, giving an algorithm of O(N*M) worst-case time-complexity.

For each value of i, get the max and min value currently in DS. Record the smallest value of max-min "so far" with the corresponding value of i.

Can one do better by implementing DS in some other way? How, or why not?

Q3 For the last one, note that 1+2+4+8+...+2^k = 2^k+1-1.

Tute 3

Q1 I believe that this gives shortest code:

(i) Write a simple (one loop) routine to reverse a[Lo..Hi], and then

(ii) reverse(0,i); reverse(i+1,j-1); reverse(j,n-1); reverse(0,n-1); -- See Bentley Programming Pearls (1986).

The above is short and runs in linear time, but there is an algorithm that is faster by a constant factor. What is it? (Consider how many times an element of the array is moved.)

See ``swapping'' in [click].

Q2 This is the ``maximum-sum interval'' problem. Bentley attributes the linear-time solution to U.Grenander in about '77.
(NB. It is not the same as the ``longest biased interval'' problem.)

Q4 Prove fs t = ff t, for all trees t.

Base case, i.e. t = emptyTree

LHS = fs emptyTree = nil = f emptyTree nil = ff emptyTree = RHS

 

general case, i.e. t = fork e L R

RHS = ff (fork e l r)

= f (fork e l r) nil -- defn of ff

= f l (cons e (f r nil)) -- defn of f

= f l (cons e (fs r)) -- induction on |r| < |t|

= append (fs l) (cons e (fs r)) -- see below[*]

= fs (fork e l r) -- defn of fs

= LHS

 

So it is useful[*] to prove that:   append (fs t) x = f t x , for all trees t, and lists x.

Base case, t = emptyTree

LHS = append (fs emptyTree) x

= append nil x = x = f emptyTree x = RHS

General case, t = fork e l r

LHS = append (fs (fork e l r)) x

= append (append (fs l) (cons e (fs r))) x -- defn of fs

= append (fs l) (append (cons e (fs r)) x) -- append is associative (can prove)

= f l (append (cons e (fs r)) x) -- induction on |l| < |t|

= f l (cons e (append (fs r) x)) -- defn of append

= f l (cons e (f r x)) -- induction on |r| < |t|

= f (fork e l r) x -- defn of f

= RHS