Tutorial 3, CSE2304, Monash, Semester 1, 2006

Week 7, begins 10 April

Class: The tutorials are the primary vehicle for practising the more formal material of the unit. Prepare your answers to the questions before the tutorial! It will probably not be possible to cover all questions unless you have prepared them in advance. Note that the online versions of the tutorials, as available at the unit's home page, are the reference documents and may contain extra information and links.
Tutors: (i) The purpose of the tutorials is not to solve the practical exercises! (ii) The purpose is to check answers, and to discuss particular sticking points, not to simply make answers available.

Objectives: The tutorials give practice in problem solving, the specification and analysis of algorithms and data-structures, and mathematics and logic useful in the above.

1. Given a linked list data structures, the foldl algorithm (fold-left) performs the cumulative operation derived from a binary function, f, and a "zero", or "unit", z:

    

   append Nil L = L

   append (Cons h t) L = Cons h (append t L)

    

   foldl f z Nil = z

   foldl f z (Cons h t) = foldl f (f z h) t

    

   e.g., foldl plus 0 [1,2,3,4] = (((0+1)+2)+3)+4 = 10, and foldl times 1 [1,2,3,4] = 4! = 24.

    

   (i) If g is associative, that is g (g x y) v = g x (g y v), for all x, y and v, and if g z w = w and g w z = w, for all w (that is z is the "zero" or "unit" element of g), prove formally that g (foldl g z L1) (foldl g z L2) = foldl g z (append L1 L2), for all lists L1 and L2.

   (ii) Give C-code for foldl(f,z,L){...}.

   (For interest's sake, there is an article on functional programming in the object-oriented language C++ here: [doi:10.1017/S0956796803004969], Mcnamara & Smaragdakis (2004).)

   
   

2. The [edit-distance] (ED), covered in lectures, tells how different two strings, S1 and S2, are, d(S1,S2)=0, if S1=S2. An optimal ED-alignment shows how to edit S1 into S2 for minimum cost.

   Here is a related but different problem to solve: The longest common subsequence (LCS) is a similarity measure, |lcs(S1,S2)|=|S1|=|S2|, if S1=S2. An optimal LCS-alignment shows the LCS of S1 and S2.
   

   (Given a sequence x₁, x₂,..., x_n, a subsequence is some (or all) of its elements, in the same order, e.g., x₂, x₄, x₅, x₇, say. A common subsequence of two sequences is a subsequence of both of them. A longest common subsequence is a common subsequence that is as long as possible.)

   (i) Give an example of two strings, S1 and S2, such that the optimal ED- and LCS-alignments are different.

   (ii) Define an algorithm to compute the length of the LCS of S1 and S2.

   (iii) Give C-code for the algorithm.

   (iv) What is the time- and space-complexity of the algorithm? Why?

   
   

3. Given the following algorithm how many times are (i) "base" and (ii) "body" executed for r(10)?

   void r(int n)
    { if( n > 0 )
       { body();
         r(n-1);
       }
      else
         base();
    }
   

   Why?

   (iii) and (iv) As above for r(n)?

   
   
4. Write a routine 'between(T,lo,hi)' which is given a binary-search tree, T, and must print all entries in T that are are between lo and hi inclusive.