首页 >
> 详细

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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- System课程作业代做、Programming作业代写、C++编程设计作业 2020-08-12
- 代写programming作业、代做python程序语言作业、代写data课 2020-08-12
- 代写software课程作业、代做r程序设计作业、代写r语言作业、代写dat 2020-08-12
- Eee2007作业代写、Programming作业代写、代做c/C++编程设 2020-08-12
- 代做spss|代写python编程|代写python程序|代写留学生 Sta 2020-08-12
- 代写sec202 代写留学生asp编程、Prolog帮写 2020-08-12
- Cs412 代写mean代写留学生jsp课程设计 2020-08-12
- 代写itnpbd7调试java作业、Java编程代写 2020-08-12
- 代写pmath 340-Assignment 2代写asp编程作业、C/C+ 2020-08-12
- Tsp课程作业代写、代做algorithms留学生作业、代做java，C/C 2020-06-23
- Kit107留学生作业代做、C++编程语言作业调试、Data课程作业代写、代 2020-06-23
- Sta302h1f作业代做、代写r课程设计作业、代写r编程语言作业、代做da 2020-06-22
- 代写seng 474作业、代做data Mining作业、Python，Ja 2020-06-22
- Cmpsci 187 Binary Search Trees 2020-06-21
- Comp226 Assignment 2: Strategy 2020-06-21
- Math 504 Homework 12 2020-06-21
- Math4007 Assessed Coursework 2 2020-06-21
- Optimization In Machine Learning Assig... 2020-06-21
- Homework 1 – Math 104B 2020-06-20
- Comp1000 Unix And C Programming 2020-06-20