Tutorial 4, CSE2304, Monash, Semester 1, 2006

Week 10, begins 8 May

Class: The tutorials are the primary vehicle for practising the more formal material of the unit. Prepare your answers to the questions before the tutorial! It will probably not be possible to cover all questions unless you have prepared them in advance. Note that the online versions of the tutorials, as available at the unit's home page, are the reference documents and 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, the specification and 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)

    

   As part of showing that algorithm u is correct, prove formally 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?

   (iii) and (iv), as above for r(n).

   
   

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