Summary

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.

1. In some correct BFS traversal starting from H, M can be traversed before N.
2. In some correct DFS traversal starting from I, E can be traversed before A.
3. In any correct DFS traversal starting from E, G must be traversed after F.
4. In any correct BFS traversal starting from K, L must be traversed after H.
5. In any correct BFS traversal starting from A, N must be traversed before G.
6. In any correct DFS traversal starting from P, A must be traversed before Q.
7. In some correct DFS traversal starting from M, Q can be traversed after K.
8. In some correct BFS traversal starting from J, A can be traversed after E.

Q2. Required knowledge covered by Topic 1.1 (5 marks)

Consider the undirected graph in Figure 2 stored by the adjacency list. For each vertex, the neighbors are arranged alphabetically (e.g., the neighbor list of A is [B,E,P]). Describe an algorithm to compute all connected components using the disjoint-set data structure. Show the tree structure after each union operation.

Q3. Required knowledge covered by Topic 1.1 (5 marks)

Consider the directed graph in Figure 3 stored by the adjacency list. The neighbors of each vertex are arranged alphabetically. Compute the topological order of vertices in the graph. Show intermediate steps.

Q4. Required knowledge covered by Topic 0 (6 marks)

We consider an undirected, unweighted graph with n vertices and m edges. Design a data structure to store the graph that can efficiently support the following three operations:
1) Scanning all neighbours of a given vertex,
2) Inserting a new edge that does not exist in the original graph
3) Deleting a vertex from the graph, including all edges related to it.
Justify the time complexity of each operation and the space complexity of the data structure.

Q5. Required knowledge covered by Topic 1.1 (5 marks)

We consider an undirected, unweighted graph with n vertices and m edges organized using an adjacency list. Design an algorithm to determine whether there exists a cycle that contains the given query vertex (i.e., the input is a vertex ID, and the result should be TRUE or FALSE). Please write your code in pseudocode and justify the time complexity of each subpart, as well as the total time complexity of your algorithm.

Q6. Required knowledge covered by Topic 1.1 (5 marks)

We consider a directed, unweighted graph stored by the adjacency list (an array of out-neighbors is stored for each vertex). Design an algorithm to compute the shortest distance between two query vertices (i.e., the input is two vertex IDs, and the output should be the shortest distance). The queue data structure is not allowed in your solution (e.g., the dequeue object in Python). Please write your pseudocode and justify the time complexity of each subpart, as well as the total time complexity of your algorithm.