COMP9312 Data Analytics for Graphs
Data Analytics for Graphs
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP9312 Data Analytics for Graphs
Assignment 1
Graph Storage and Graph Traversal
Summary
Submission Submit an electronic copy of all answers on Moodle (only the last submission will be used).
Required Files A .pdf file is required. The file name should be ass1_Zid.pdf
Deadline 9pm Friday 23 June (Sydney Time)
Marks 30 marks (15% toward your total mark for this course)
Late penalty. 5% of max mark will be deducted for each additional day (24hr) after the specified submission time and date. No submission is accepted 5 days (120hr) after
the deadline.
START OF QUESTIONS
Figure 1 Figure 2
Q1. Required knowledge covered by Topic 1.1 (4 marks)
Please determine whether the following statements for the graph in Figure 1 are TRUE or FALSE. (4 marks)
a. In some correct BFS traversal starting from C, A can be traversed before F.
b. In any correct DFS traversal starting from E, G must be traversed after F.
c. In any correct BFS traversal starting from B, I must be traversed after C.
d. In some correct DFS traversal starting from I, F can be traversed before A.
Marking for Q1: 1 mark is given for each correct TRUE/FALSE answer.
Q2. Required knowledge covered by Topic 0 (6 marks)
Consider the undirected graph in Figure 1 stored by the adjacency list. For each vertex, the neighbors are arranged alphabetically (e.g., the neighbor list of A is [B,C,E,I]). Describe
the algorithm to compute all connected components by the disjoint-set data structure. Show the tree structure after each union operation.
Marking for Q2: Full marks are given if each intermediate disjoint-set tree structure is correct.
Q3. Required knowledge covered by Topic 1.1 (6 marks)
Consider the directed graph in Figure 2 stored by the adjacency list. Compute the topological order of vertices in the graph. Show intermediate steps.
Marking for Q3: Full marks are given if the described process of each vertex is correct and the order of vertices are correct.
Q4. Required knowledge covered by Topic 1.1 (7 marks)
We consider an undirected unweighted graph with n vertices and m edges organized by the adjacency list. Given two vertex sets X and Y in the graph, the sizes of two sets are
x=|X|, y=|Y|. Design an algorithm to compute the shortest distance bewteen X and Y (i.e., the smallest shortest distance between all possible pair of vertices from X to Y). Justify
the time complexity of your algorithm.
Marking for Q4: Two factors are evaluated in marking: (1) How good is your time complexity; (2) Does your algorithm match your time complexity. Full marks are given if
your time complexity is not larger than our expected one and your algorithm corresponds with your time complexity.
Q5. Required knowledge covered by Topic 0 (7 marks)
A streaming graph is a graph where edges are added continuously over time. The graph constructed by L most recent arriving edges is defined as the sliding window. An example
in Figure 3 shows a streaming graph with four edges arriving sequentially. The sliding windows for t=3 and t=4 are presented. Given L=3, when the edge (B,C) arrives, the edge
(A,B) expires and is deleted from the sliding window.
Given a streaming graph without any duplicate edge, provide a data structure to efficiently maintain the neighbors of each vertex within the sliding window. Specifically, the data
structure should support three operations: 1) scanning all neighbors of the vertex in the sliding window, 2) inserting a new neighbor when a new edge arrives, and 3) deleting the
expired neighbor. Justify the time complexity of each operation.
Figure 3: The edges (A,B), (C,D), (A,C), and (B,C) are sequentially added to the graph.
Marking for Q5: Two factors are evaluated in marking: (1) How good is your time complexity; (2) Does your algorithm match your time complexity. Full marks are given if your
time complexity is not larger than our expected one and your algorithm corresponds with your time complexity.