COMP2011 Tutorial Exercises, Week 11

Directed Graphs, Dijkstra's Algorithm

Tutorial Questions

1. Directed Graphs (G&T Chap 13)

   R-12.5 Bob loves foreign languages and wants to plan his course schedule for the following years. He is interested in nine language courses, with prerequisites as follows:

   • LA15: (none)
   • LA16: LA15
   • LA22: (none)
   • LA31: LA15
   • LA32: LA16, LA31
   • LA126: LA22, LA32
   • LA127: LA16
   • LA141: LA22, LA16
   • LA169: LA32
   
   a) Use a directed graph to find a sequence of courses that allows Bob to satisfy all the prerequisites.
   b) Use the Floyd-Warshall algorithm to compute the transitive closure of the directed graph from part (a). What relationship does this graph represent?

2. Minimum Spanning Trees (G&T Chap 13)

   R-12.17 There are eight small islands in a lake, and the state wants to build seven bridges to connect them so that each island can be reached from any other one via one or more bridges. The cost of constructing a bridge is proportional to its length. The distances between pairs of islands are given in the following table.

   	2	3	4	5	6	7	8
   1	248	210	340	280	200	345	120
   2		265	175	215	180	185	155
   3			260	115	350	435	195
   4				160	330	295	230
   5					360	400	170
   6						175	205
   7							305

   
   Find which bridges to build so that the total construction cost is mimimum, using

   a) Kruskal's algorithm
   b) the Prim-Jarník algorithm

3. Any Questions about Assignment 3.