CSSE, Monash, .au, CSE2304, Tutorial #5, semester 1, 2001
Group B: week 11, 14 May...
Group A: week 12, 21 May...

Class: Your answers must be prepared before the tute.

1. Integration is covered in the last lectures of the subject but you can do some reading ahead. Integration is the process of finding the area under a curve, f(x), between x=a and x=b, for some a and b, where a<=b. The simplest method is the (non-adaptive) [rectangle rule (click)]: Divide the interval [a,b] into N subintervals of equal width. Approximate the integral over each subinterval by a rectangle.
   The non-adaptive rectangle rule is not accurate if the function changes quickly and N is small.
   Give an algorithm for a simple adaptive rectangle rule: The adaptive version uses more subintervals where the function changes quickly. It compares the values of f(x) at the ends of each subinterval. If the difference in values is less than a small constant, `epsilon', the function is assumed to vary slowly in this region, and the integral over the subinterval is approximated by a rectangle, as before. If the difference in values is greater than epsilon, integrate over the subinterval using a finer subdivision.
   
   
2. Give a [recursive] algorithm to generate all strings consisting of n pairs of matched parentheses e.g.
   

     n=1: ()
     n=2: (()),  ()()
     n=3: ((())), (()()),  (())(),  ()(()), ()()()
     etc.
   

   Note that you can only close, ')', an already open '('.
   
   
3. Draw an undirected, weighted [graph] representing the capital cities of Australia {Adelaide, Brisbane, Canberra, Darwin, Hobart, Melbourne, Perth, Sydney} and the air-routes between them flown by jet aircraft (as far as you know or estimate).
   Use
   1. Kruskal's algorithm
   2. Prim's algorithm
   to find a minimum spanning tree of the cities in your graph.

© 2001, L. Allison, Comp. Sci. & SWE, Monash University, Australia