代做CSI 403留学生、Data Structures代写、代做Java，c++程序设计、代写Python语言

日期：2019-12-05 10:32

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.