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

Weeks 11 and 12, 17 to 28 May 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. A "strict" binary tree is either a Leaf, or a Fork which contains exactly (not at most) two strict binary subtrees, e.g.

   Tree a b = L a | F b (Tree a b) (Tree a b)

   The structure of such a tree can be represented by the sequence of its node types in prefix order, e.g.

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

   (i) There is always one more L than F in such a sequence, why?

   (ii) Give C-code to print out all the sequences corresponding to trees containing exactly n Forks, where n>=0.

2. In [numerical integration] of a function, f(), one does not always know in advance what size the interval should be for a fast and accurate result. One simple strategy is to start with some initial interval size and to keep halving it, thus doubling the number of intervals, nIntervals, until the result (integral) changes by no more than some small value epsilon.

   Write efficient C-code

   float adaptive(float f(float), float lo, float hi, int nIntervals, float epsilon)

   to use this strategy with the trapezoidal rule.

3. Draw a directed acyclic graph (DAG) showing at least 9 CSSE units, some from years 1, 2 and 3, CSE1*, CSE2*, CSE3*, and including core units, with edges showing prerequisite relations.
   Find a critical path for your graph.