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

5 to 16 May 2003

Class: Prepare your answers to the questions before the tute!

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. It will not be possible to cover all questions if the class has not prepared them all in advance.

Provided that the tute has been well prepared, the tutor may lead a general discussion on graphs and prac'4 once the tute questions have been dealt with.

1. Choose a (G-rated) soap-opera (e.g. Neighbours, Secret Life of Us, ...), play, film or novel, and gather data on who hugs or kisses who. Draw a graph (vertices and edges) representing the data. Should the graph be:
   • Directed?
   • Weighted?
   • Connected?
   • Bipartite?
   • Acyclic?
   In each case say why or why not.
   
   In your graph which two individuals are connected but as far apart as possible (in terms of numbers of edges).
   
   
2. Draw a graph representing at least eight CSE subjects, including the core 1st and 2nd year programming subjects and at least two 3rd-year subject. You can find the full list of IT subjects, including prerequisites, here:  http://www.monash.edu.au/pubs/handbooks/units/index-byFaculty-IT.html.
   Draw an edge from subject p to q if p is a pre-requisite for q.
   • Are there / should there be cycles in the graph?
   • What is the minimum number of semesters required to take all of the subjects in your graph? Why?