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

Weeks 12-13,  23 May to 3 June

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. Given the following algorithm, how many times are (i) "base" and (ii) "body" executed for r(10)?

   void r(int n)
    { if( n > 0 )
       { r(n-1);
         body();
         r(n-1);
       }
      else
         base();
    }
   

   Why?

   
   

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 algorithmic solution to this problem 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.

   
   

4. Here is a rough idea for a sorting algorithm:

   Move all the even elements, if any, to one end of the array and move all the odd elements, if any, to the other end of the array.

   Somehow[*], sort all the even elements and sort all the odd elements.

   Do whatever else is necessary, if anything, to ensure that the entire array is sorted.

   Design an algorithm from this rough idea and state its time and space complexity.

   [*] Note that even/odd involves testing the least significant bit. What about the next bit?