## 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.