Tutorial 2, CSE2304, CSSE, Monash, Semester 1, 2005

Weeks 5-6,  4 to 15 April

Class: Prepare your answers to the questions before the tutorial! It will probably not be possible to cover all questions unless the class has prepared them all in advance. (The online versions of the tutorials 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, 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?

   
   

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 permutation of n things is a sequence of the n things in some order. E.g., [1,2,3] and [3,1,2] are both permutations of the set of things {1,2,3}.

   Permutations of {1..n} can be ordered lexicographically, e.g., [1,2,3] < [1,3,2] < [2,1,3] < [2,3,1] < [3,1,2] < [3,2,1].

   (i) If n=7, what is the next permutation after [4,7,5,2,6,3,1]?

   (ii) Give C-code for an algorithm, next(int n, int p[]), which is given a permutation of {1..n} in p[] and which changes p[] so that it holds the next permutation in lexicographical order (assuming there is one).

   (iii) Give a formal, logical argument (as in [e.g.] & other examples) that your routine (a) terminates and (b) is correct.