CSI 403 Data Structures and Algorithms Fall 2019
Homework V Hurd
Question 1 [25 pts]
Consider the following disjoint set (DS) S : {{0, 1, 2]; {3, 5}} assuming the first listed element is
the representative for each set.
(a)[5pts] Show the data structure of the disjoint set using both the list and tree
representation. Multiple tree representations are possible based on how unions were applied
to get to these sets. Include possible rank values as well.
Consider the following commands applied to S:
make set(4)
union(1,5)
union(4,5)
(b)[10pts] Show the resulting data structure after applying the commands on the list
representation, assuming the weighted union heuristic is employed.
(c)[10pts] Show the resulting data structure after applying the commands on the tree
representation, assuming both the path-compression and union-by-rank heuristics are
employed (show the ranks before and after the commands).
Question 2 [25 pts]
(a)[10pts] Give an algorithm (pseudo code) to detect whether a given undirected graph
contains a cycle: a sequence of nodes that starts and ends in the same node without traversing
the same edge twice.
(b)[10pts] If the graph contains a cycle, then your algorithm should output one example
cycle as the sequence of nodes that are on the cycle. (It should not output all cycles in the
graph, just one of them.) The running time of your algorithm should be O(m + n) for a graph
with n nodes and m edges.
(c)[5pts] Demonstrate the steps of your algorithm on a simple “ring" graph of 5 nodes:
E : {(1; 2); (2; 3); (3; 4); (4; 5); (5; 1)}.
Note: To get points for (b) and (c) you need to have solved (a).
Question 3 [25 pts]
We have a connected undirected graph G = (V, E), and a specific vertex u ϵ V. Suppose we
compute a depth-first search tree rooted at u, and obtain a tree T that includes all nodes of G.
Suppose we then compute a breadth-first search tree rooted at u, and obtain the same tree T.
Prove that G = T. (In other words, if T is both a depth-first search tree and a breadth-first search
tree rooted at u, then G cannot contain any edges that do not belong to T.)
Hint: Consider a proof by contradiction.
CSI 403 Data Structures and Algorithms Fall 2019
Homework V Hurd
Question 4 [25 pts]
Members of the Stark family do not get along with those from the Lannister family. Between
any pair of people, there may or may not be an active rivalry edge.
(a)[5 pts] Show a small example of 4 people and 4 rivalry edges such that each person is
in at least one rivalry and each person is assigned as either a Stark or a Lannister in a way that
rivalries are only between a Stark and a Lannister. (If you wish, you can add first names of the
people in your example, but this is not obligatory). Is the same example possible if we have 5
unique rivalry edges instead of 4? Explain your answer.
(b)[20 pts] Suppose we have n people in total and we have a list of r pairs of those
people for which there are rivalry edges. Give an O(n + r)-time algorithm (pseudo code) that
determines whether it is possible to designate some of the people as Starks and the remainder
as Lannisters such that each rivalry is between a Stark and a Lannister. If it is possible to
perform such a designation, your algorithm should produce it.
Question 5 [Extra: 10 pts]
From the book: In class we mentioned how the discovery and finish times of all nodes in a DFS
follow a nested parenthesis structure. Examine figure 22.5 that shows the parenthesis structure
of a specific DFS in part (b). Show a similar parenthesis structure for the DFS from figure 22.4,
i.e. draw an analog of figure 22.5(b) that pertains to the DFS from figure 22.4.