首页 >
> 详细

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
- 微信：codinghelp

- 代写cs3014 Google Analytics Customer Rev 2020-01-21
- 代写cmpsc121 Structs代写留学生c/C++实验... 2020-01-21
- 代写mis6326 Data Management调试存储过程作业、数据库编 2020-01-21
- 代写msci 581作业、代做marketing Analytics作业、P 2020-01-20
- Software课程作业代做、代写java，C/C++程序设计作业、Pyth 2020-01-20
- Tcss 372作业代做、代写python，Java编程语言作业、代做c/C 2020-01-20
- Emergency Facilities作业代写、代写r编程设计作业、R课程 2020-01-18
- Cis 413/513作业代做、代写data Structures作业、Ja 2020-01-18
- 代写ia626留学生作业、Python程序设计作业调试、代做data课程作业 2020-01-18
- Mat00027i作业代写、Java程序语言作业调试、Mathematica 2020-01-17
- 代做kt Model作业、代写java，Python编程设计作业、代做c/C 2020-01-17
- Data Set课程作业代做、代写r程序语言作业、Ltcret留学生作业代做 2020-01-17
- 代写rstudio留学生作业、代做r编程设计作业、代写r课程设计作业代做数据 2020-01-17
- 代写cs2250 Delimiter Matching代做数据结... 2020-01-16
- 代写cs12b Edit Distance帮写java实验作业... 2020-01-16
- 代写mins325 Filereader And Filewriter代... 2020-01-16
- 代写cosi131 Tunnels帮写java实验作业 2020-01-16
- 代写inm312 Balancebit Software代写留学... 2020-01-16
- 代写cs61b Maze Solver代写java课程设计 2020-01-16
- Program留学生作业代做、C/C++编程语言作业代写、代做java，Py 2020-01-14