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);
             body;
             r(n-1);
           }
          else
             base;
        }
   

   Why?

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:
   • Only consider stations on or inside the Circle Line (yellow).
   • Make a vertex for each station shown by an open circle, e.g. Victoria, or by 2 or 3 linked open circles, e.g. South Kensington.
   • Make an edge between v1 and v2 if there is a direct line between the two vertices (e.g. Victoria and South Kensington) with no other vertex-station in between.
   • The weight of an edge (v1,v2) is one plus the number of non-vertex stations (indicated by "ticks", e.g. Sloane Square) on the line between v1 and v2.
   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.