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

24 March to 4 April 2003

Class: Prepare your answers to the equestions before the tute!

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. It will not be possible to cover all questions if the class has not prepared them all in advance.

1. x, y and z are integer variables. Give C-code to determine if exactly two of x, y and z are odd. Use as few operators (+, -, ..., & |, &&, ..., odd(), even(), etc.) as possible.
2. Given: A[0..N-1] an array of N integers, not necessarily distinct, and M<<N.
   max(A[i..i+M-1]) is the largest value in that interval and min(A[i..i+M-1]) is the smallest value in the interval.
   Give an efficient algorithm to find the most stable interval A[i..i+M-1] in A, i.e. such that max(A[i..i+M-1])-min(A[i..i+M-1]) is as small as possible.

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 for... Lo1 Hi1 Lo2 Hi2 1 8 1 8 1 8 i 8 0 8 0 i 0 n 1 i 0 n-1 1 2*i 0 n-1 1 2**i NB. for i from 3 to 5 do body end_for -- body executed thrice.  And 2**i = 2i.

4. A strict binary tree is made of fork and leaf nodes (only), where every fork node has exactly two sub-trees (not ``at most two'').

   F . . . . L F <----> FLFLL . . L L

   Such a tree can be represented by its prefix traversal string, writing `F' for a fork and `L' for a leaf. Note that the string has one more `L' than `F', and no prefix of the string has that property. Every tree has such a string and the tree can be reconstructed from the string. The set of all such strings representing strict binary trees can therefore be put in an ordered series, first by length and within that lexicographically (alphabetically), i.e. L, FLL, FFLLL, FLFLL, ...
   Give the next six strings in the series.
   Give an algorithm to change a valid string, S, into the next string in the series.