Description
1. [10%] Show that there can be more than one minimum spanning tree in an undirected graph by
giving an example.
2. [10%] Briefly yet clearly describe how to tell whether an undirected graph is connected or not.
3. [10%] Briefly describe how to determine whether a directed graph has a cycle using the depth
first search algorithm.
4. [15%] Suppose that we have n professional wrestlers and a list of r pairs of wrestlers for which
there are rivalries. (Between any pair of wrestlers, there may or may not be a rivalry.) Give an
O(n+r) time algorithm that determines whether it is possible to designate some of the wrestlers
to Red team and the remainder as Blue team such that each rivalry is between a Red and a Blue
team member. If it is possible to perform such an assignment, your algorithm should produce it.
5. [20%] Use Prim’s algorithm to find the minimum spanning tree in the following graph starting
from vertex A. Show every step.
6. [15%] Using Floyd’s algorithm, find all pairs shortest paths in the following graph.
7. [20%] Find the longest common subsequence between two strings ABCE and ABDC via dynamic
programming.
CS575
