Tutorial 2, CSE2304, Monash, Semester 1, 2006

Week 5, begins 27 March

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. 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 curried: Cons p1 p2 rather than Cons(p1, p2), and append p1 p2 rather than append(p1, p2).

   
   

2. 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.

   
   

3. Given the following algorithm:

   for i from Lo1 to Hi1 do
      for j from Lo2 to Hi2 do 
         body 
      end_for 
   end_for
   

   How many times is body executed if

   1. Lo1=1, Hi1=10, Lo2=i, Hi2=10,
   2. Lo1=0, Hi1= 9, Lo2=0, Hi2= 9,
   3. Lo1=1, Hi1=n, Lo2=i-2, Hi2=i+2,
   4. Lo1=0, Hi1=n, Lo2=i, Hi2=2*i ?

   
   

4. 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.