Tute 2, CSE2304, CSSE, Monash, Semester 1, 2004

Weeks 4 and 5, 22 March to 2 April 2004

Class: Prepare your answers to the questions before the tute! It will probably not be possible to cover all questions unless the class has prepared them all in advance. (The online versions of the tutes may contain extra information and links.)

Tutors: (i) The purpose of the tutorials is not to solve the prac's! (ii) The purpose of the tutorials is to check answers, and to discuss particular sticking points, not to simply make answers available.

1. Here are some definitions to do with 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)

    

   Prove formally that   length(append a b) = (length a) + (length b), for all lists `a' and `b'.

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

5. 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. 5: 1+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.