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

Weeks 10-11,  9 to 20 May

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. The "unique" algorithm, u, (also known as "nub") removes duplicate entries from linked 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 that algorithm u is correct, that is prove formally (in the style of [e.g.]) that  member v w = member v (u w), for all v and all lists w.

   
   

2. A problem to solve: 2004 was 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.

   
   

3. Given the following algorithm, how many times are (i) "base" and (ii) "body" executed for r(1000)?

   void r(int n)
    { if( n > 1 )
       { body();
         r(n/2);
       }
      else
         base();
    }
   

   Why?

   
   

4. Find the London Tube (Underground) Map in the 'net (e.g. it was [here] as of 2/2005). 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.

   (i) What is the shortest path, according to the graph, between Tottenham Court Road and Victoria?

   (ii) Find a minimum spanning tree of the graph.