CSCI2100C : Assignment 4 Part 2

$30.00

Category: You will Instantly receive a download link for .zip solution file upon Payment || To Order Original Work Click Custom Order?

Description

5/5 - (13 votes)

Q1. [38 marks] Consider the directed graph 𝐺1 as shown in Figure 1. Answer the
following questions.
𝑣1 𝑣2
𝑣3 𝑣4
𝑣5
𝑣6
𝑣7
𝑣8
Figure 1. Directed graph for Q1
– (i). [4 marks] Calculate the out-degree of𝑣3 and the in-degree of𝑣8. (Refer to CSCI2100CLecture22 Page 11)
– (ii). [8 marks] For 𝐺1, show both its adjacency list representation and its adjacency
matrix representation. (Refer to CSCI2100C-Lecture22 Pages 17-20)
– (iii). [10 marks] Traverse 𝐺1 using breadth-first search with 𝑣1 as the source, assuming that the out-neighbors of a node are visited in ascending order of ID. Show the
process and the content of the queue 𝑄 step by step. You may use 0 to denote the
color to be white, 1 to denote the color to be gray, and 2 to denote the color to be
black. (Refer to CSCI2100C-Lecture22 Pages 24-28)
– (iv). [8 marks] According to the results of Part (iii), show the contents of minlength
array and prev array respectively. (Refer to CSCI2100C-Lecture22 Pages 34-35)
– (v). [4 marks] Show how to get the minimum length path from the source 𝑣1 to 𝑣4
using the minlength array and prev array. Justify your answer.
– (vi). [4 marks] Draw the BFS tree. (Refer to CSCI2100C-Lecture22 Page 36)
βˆ—Departmental Guideline for Plagiarism (Department of Systems Engineering and Engineering Management):
If a student is found plagiarizing, his/her case will be reported to the Department Examination Panel. If the
case is proven after deliberation, the student will automatically fail the course in which he/she committed
plagiarism. The definition of plagiarism includes copying of the whole or parts of written assignments, programming exercises, reports, quiz papers, mid-term examinations and final examinations. The penalty will
apply to both the one who copies the work and the one whose work is being copied, unless the latter can
prove his/her work has been copied unwittingly. Furthermore, inclusion of others’ works or results without
citation in assignments and reports is also regarded as plagiarism with similar penalty to the offender. A student caught plagiarizing during tests or examinations will be reported to the Faculty office and appropriate
disciplinary authorities for further action, in addition to failing the course.
β–  Q2. [26 marks] A directed graph 𝐺2 is shown in Figure 2. Assume that we use depthfirst search (DFS) to check if 𝐺2 is a DAG and the permutation of nodes to do DFS on
𝐺2 is (𝑣2, 𝑣3, 𝑣4, 𝑣5, 𝑣6, 𝑣1, 𝑣7). During a DFS traversal, assume that the out-neighbors of
a node are visited in ascending order of ID. Answer the following questions.
𝑣1
𝑣2
𝑣3
𝑣4
𝑣5
𝑣6
𝑣7
Figure 2. Directed Graph 𝐺2 for Q2
– (i). [7 marks] Show the first discovery time and finish time of each node. (Refer to
CSCI2100C-Lecture24 Pages 5-6)
– (ii). [4 marks] Draw the DFS trees. (Refer to CSCI2100C-Lecture24 Page 7)
– (iii). [11 marks] Classify edges according to the interval of each node derived from
Part (i). You should explicitly output the type of each edge. Justify your answer. (Refer
to CSCI2100C-Lecture24 Page 8)
– (iv). [4 marks] Show why𝐺2 is (or is not) a DAG using the results in Part (iii). Justify
your answer. (Refer to CSCI2100C-Lecture24 Page 11)