1. Find a topological ordering for the graph in Figure 9.81
2. Consider the directed graph shown in the figure below. Apply Dijkstra’s algorithm with vertex S
as source and find the shortest path to all other vertices. Show all steps
3. Use Floyd-Warshall Algorithm to get all-pair shortest path for the following graph. Show the final distance matrix and path matrix.
4. The input is a list of league game scores (and there are no ties). If all teams have at least one win and a loss, we can generally prove, by a silly transitivity argument, that any team is better than any other. For instance, in the six-team league where everyone plays three games, suppose we have the following results: A beat B and C; B beat C and F; C beat D; D beat E; E beat A; F beat D and E. Then we can prove that A is better than F, because A beat B, who in turn beat F. Similarly, we can prove that F is better than A because F beat E and E beat A.
Given a list of game scores and two teams X and Y, write an algorithm in pseudo code to either find a proof ( if one exists) that X is better than Y, or Y is better than X, or indicate that no
proof of this form can be found.
5. A student needs to take a certain number of courses to graduate, and these courses have prerequisites that must be followed. Assume that all courses are offered every semester and that the student can take an unlimited number of courses per semester. Given a list of courses and their prerequisites, write an algorithm in pseudocode to computer a schedule that requires the minimum number of semesters.
6. Give an algorithm to find a maximum spanning tree. Is this harder than finding a minimum spanning tree
7. Find all the articulation points in the graph in Figure 9.85. Show the depth-first spanning tree and
