^CSE2304^
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.
 x, y and z are integer variables.
Give Ccode to determine if exactly two
of x, y and z are odd.
Use as few operators (+, , ..., & , &&, ..., odd(), even(),
etc.) as possible.
 Given: A[0..N1] an array of N integers, not necessarily distinct, and
M<<N.
max(A[i..i+M1]) is the largest value in that interval and
min(A[i..i+M1]) is the smallest value in the interval.
Give an efficient algorithm to find the most stable
interval A[i..i+M1] in A,
i.e. such that max(A[i..i+M1])min(A[i..i+M1])
is as small as possible.
 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  n1  1  2*i 
0  n1  1  2**i 
NB. for i from 3 to 5 do body end_for  body executed thrice.
And 2**i = 2^{i}.

 A strict binary tree is made of fork
and leaf nodes (only), where every fork node has
exactly two subtrees (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.
© L. Allison 2003,
School of Computer Science and Software Engineering,
Monash University, Australia 3800.
Created with "vi (Linux & Solaris)", charset=iso88591