^CSE2304^
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 datastructures, and
mathematics and logic useful in the above.

 Given a linked list data structures,
the foldl algorithm (foldleft) 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 Ccode for foldl(f,z,L){...}.
 (For interest's sake, there is an article on functional programming
in the objectoriented language C++ here:
[doi:10.1017/S0956796803004969],
Mcnamara & Smaragdakis (2004).)

 The [editdistance] (ED),
covered in lectures, tells how different
two strings, S1 and S2, are, d(S1,S2)=0, if S1=S2.
An optimal EDalignment 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 LCSalignment shows the LCS of S1 and S2.
 (Given a sequence x_{1}, x_{2},..., x_{n},
a subsequence is some (or all) of its elements, in the same order,
e.g., x_{2}, x_{4}, x_{5}, x_{7},
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 LCSalignments are different.
 (ii) Define an algorithm to compute the length of the LCS of S1 and S2.
 (iii) Give Ccode for the algorithm.
 (iv) What is the time and spacecomplexity of the algorithm? Why?

 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(n1);
}
else
base();
}
 Why?
 (iii) and (iv) As above for r(n)?

Write a routine 'between(T,lo,hi)'
which is given a binarysearch tree, T,
and must print all entries in T that
are are between lo and hi inclusive.
© 2006
L. Allison,
Faculty of Information Technology (Clayton),
was School of Computer Science and Software Engineering,
Monash University,
Australia 3800.
Created with "vi (Linux & Solaris)", charset=iso88591