Prac 5, CSE2304, CSSE, Monash, Semester 1, 2002

Group A: week 12, 27 - 31 May,
Group B: week 13, 3 - 7 June

Candidate: You must prepare your solution to this programming exercise in advance. The designated platform, on which your solution must be demonstrated and on which it will be marked, is the `gcc' compiler running on `Linux'. If you develop a solution on another platform, it is your responsibility to ensure that it works correctly on the designated platform. Read the information under the [prac' guide], [on C and code modularity] and [plagiarism] links on the subject home page.

Groups: Note that different prac'-groups might be set different tasks. Make sure that you do your task. You will get zero marks if you solve the wrong problem.

Group A

Extend your program from [prac4] as follows:

A [topological sort] of an acyclic graph is an ordering of the vertices of the graph such that the edges all point forwards in the ordering.

Task: Extend your program so that it prints the event-descriptions in a topologically sorted order. This would be one possible way of telling the story in a linear way, without "flash-backs". (Any topological sort of the events will do.)

[6 marks]

Group B

Extend your program from [prac4] as follows:

After reading the number, `r', of a given page, your program must print the most distant page that is accessible by following a path of links from `r'. i.e. it must print the page, `d', which has the largest (finite), shortest-distance from r.
Print d, d's description, the distance,

[4 marks]
and also the shortest path from r to d.
[2 marks]

e.g. You might adapt Dijkstra's or Floyd's [algorithms].

© L. Allison, School of Computer Science and Software Engineering, Monash University, Australia 3800.
Created with "vi (Linux & IRIX)",   charset=iso-8859-1