Assignment #4 Solution

1. Babyfaces vs. Heels. [10 marks total]

There are two types of professional wrestlers: “babyfaces” (the good guys) and “heels” (the bad guys). Between any pair of wrestlers there may or may not be a rivalry. Suppose there are n wrestlers and we have a list of r pairs of wrestlers for which there are rivalries.

 

(a) Give an algorithm that determines whether it is possible to designate some of the wrestlers as babyfaces and the remainder as heels such that each rivalry is between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it.

 

 (b) What is the worst-case run time of your algorithm?

 

 

2. DFS of a Directed Graph. [10 marks total]

Given the following directed graph, traverse the graph by depth-first search

(DFS) starting at vertex a and visiting vertices in alphabetical order.

 

(a) Label each vertex with its discovery and finish time

 

 

 (b) Construct the corresponding DFS forest in the standard form.

 

 

(c) Classify each edge as a tree (T), forward (F), back (B), or cross (C) edge.

 

3. Connected Components. [10 marks total]

 

Show how to modify depth-first search (DFS) of an undirected graph G to identify the connected components of G, and that the depth-first forest contains as many trees as G has connected components. More precisely, show how to modify DFS so that it assigns to each vertex v and integer label between 1 and k, where k is the number of connected components of G, such that the labels of two vertices u and v are equal if and only if u and v are in the same connected component.

 

4. Minimum Spanning Tree (MST) Algorithms. [20 marks total]

 

All answers in question 4 will use the following pseudo-code API:

 

vertex From(vertex To, int Weight)

 

if Weight is blank, no valid path is present in graph / answer not yet available

 

(a) Apply Prim’s algorithm to the following graph. Include in the priority queue all the vertices not already in the tree.

(b) Now, apply Prim’s algorithm to the following graph. Include in the priority queue only the fringe vertices (the vertices not in the current tree which are adjacent to at least one tree vertex).

 

 

 

(c) Apply Kruskal’s algorithms to find a MST in the graph below and also to the graph in part (b).

 

5. Second-best Minimum Spanning Tree (MST). [15 marks]

 

Let G = (V, E) be an undirected, connected graph whose weight function is w : E

→ R, and suppose that |E| ≥ |V | and all edge weights are distinct.

We define the second-best minimum spanning tree as follows. Let T be the set of

all spanning trees of G, and let T be a MST of G. Then a second-best minimum spanning tree is a spanning tree T such that w(T) = minT′′∈(T −T′){w(T′′)}.

 

(a) Show that the MST is unique, but that the second-best MST need not be unique.

edges (u,v) ∈ T and (x,y) ∈ T such

 

 

(c) Given an efficient algorithm to compute the second-best MST of G.

 

 

 

6. Variations of Dijkstra’s Algorithm. [15 marks]

 

Explain what adjustments if any need to be made in Dijkstra’s algorithm and/or in an underlying graph to solve the following problems.

 

(a) Solve the single-source shortest-paths problem for directed weighted graphs.

 

 

(b) Find a shortest path between two given vertices of a weighted graph of digraph. (This variation is called the single-pair shortest-path problem.)

 

(c) Find the shortest paths to a given vertex from each other vertex of a weighted graph or digraph. (This variation is called the single-destination shortest-paths problem.)

 

 

7. Dijkstra’s Algorithm graph. [10 marks]

Trace the Dijkstra’s algorithm on the graph in Question 4(b) with vertex a as the source.

 

L(v) depicts the minimum path length of edges from source to v.

8. Disjoint Sets. [10 marks]

 

Professor Gump suggests that it might be possible to keep just one pointer in each set object, rather than two (head and tail), while keeping the number of pointers in each list element at two. Show that the professor’s suggestion is well- founded by describing how to represent each set by a linked list such that each operation Make-Set, Union, and Find-Set has the same running time as the operations using the standard linked list representation of disjoint sets. Describe also how the operations work. Your scheme should allow for the weighted-union heuristic, with the same effect.

 

 

Make-Set(Element e): O(1), linear time

 

Find-Set(Element e): O(1), linear time

 

Union(Set s, Set t): O(L), where L is the length of the set appended

 

Weighted-union heuristic: