Description
1. Find a topological ordering for the graph in Figure 9.81 [5 points]
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. [10 points]
3. Use Floyd-Warshall Algorithm to get all-pair shortest path for the following graph. Show the final
distance matrix and path matrix. [10 points]
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 points]
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. [5 points]
6. Give an algorithm to find a maximum spanning tree. Is this harder than finding a minimum spanning
tree. [5 points]
7. Find all the articulation points in the graph in Figure 9.85. Show the depth-first spanning tree and
the values of Num and Low for each vertex. [10 points]
