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

Weeks 9 and 10, 3 to 14 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. 2004 is a leap year because it is divisible by 4, although 1900 was not because it is also divisible by 100, but there again 2000 was because it is also divisible by 400.
    Give a short piece of C-code to determine if `year' is a leap year.

  2. Here are some definitions to do with lists:
    List e = Nil | Cons e (List e)
    member x Nil = False
    member x (Cons y ys) = (x == y) || (member x ys)
    u Nil = Nil
    u (Cons x xs) = if  member x xs  then  u xs  else  Cons x (u xs)
    Prove formally that   member v w = member v (u w), for all v and all lists w.

  3. How many times are (i) "base" and (ii) "body" executed for r(10)?
    void r(int n)
         { if( n > 0 )
            { r(n-1);

  4. Find the London Tube (Underground) Map in the 'net (e.g. it was [here] as of 3/2/2004). Draw an undirected weighted graph based on the map as follows:
    1. What is the shortest path, according to the graph, between Tottenham Court Road and Victoria?
    2. Find a minimum spanning tree of the graph.

© L. Allison 2004, School of Computer Science and Software Engineering, Monash University, Australia 3800.
Created with "vi (Linux & Solaris)",   charset=iso-8859-1