COMP2011 Tutorial Exercises, Week 11

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.

2345678
1  248210340280200345 120
2265175215180185155
3260115350435195
4160330295230
5360400170
6175205
7305

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.