Tutorial 2, CSE2304, Monash, Semester 1, 2006
Week 5, begins 27 March
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.
(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.
The tutorials give practice in
the specification and analysis of algorithms and data-structures, and
mathematics and logic useful in the above.
- Here are definitions of a list type for the linked-list data structure
and of two algorithms, append and length, on lists:
- List e = Nil | Cons e (List e)
- append Nil ys = ys
- append (Cons x xs) ys = Cons x (append xs ys)
- length Nil = 0
- length (Cons x xs) = 1 + (length xs)
- (i) Prove formally that
length(append a b) = (length a) + (length b),
for all lists a and b.
- (ii) Which expression is faster to evaluate,
the left or right hand side of the equality in (i)? Why?
- (iii) How could a compiler use such equalities?
- Note that Cons and append are
Cons p1 p2 rather than
Cons(p1, p2), and
append p1 p2 rather than
- A problem to solve:
x, y and z are floating point variables.
Give a short piece of C-code to find
the median value of x, y, and z.
- Given the following algorithm:
for i from Lo1 to Hi1 do
for j from Lo2 to Hi2 do
- How many times is body executed if
- Lo1=1, Hi1=10, Lo2=i, Hi2=10,
- Lo1=0, Hi1= 9, Lo2=0, Hi2= 9,
- Lo1=1, Hi1=n, Lo2=i-2, Hi2=i+2,
- Lo1=0, Hi1=n, Lo2=i, Hi2=2*i ?
- A partition of an integer, n,
is a list of positive integers that add up to n.
Here, each partition is written in non-increasing order,
e.g.. 3+2, not 2+3.
- Partitions can be ordered lexicographically,
e.g., for n=5:
1+1+1+1+1 < 2+1+1+1 < 2+2+1 < 3+1+1 < 3+2 <
4+1 < 5.
- (i) Write a C routine,
next(int length, int p),
which is given a (non-increasing) partition and
prints the partition, if any, that comes next in
lexicographical order. e.g. Given 2+1+1+1, print 2+2+1.
- (ii) Is it always (for all n) the case that the
next partition is necessarily the same length or shorter
than the current one, or not?
Say why or give a counter-example.
- (iii) Give a formal argument that your routine
(a) terminates and (b) is correct.
Faculty of Information Technology (Clayton),
was School of Computer Science and Software Engineering,
Created with "vi (Linux & Solaris)", charset=iso-8859-1