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 v₈, v₁₃ can be traversed before v₄.
2. In some correct DFS traversal starting from v₉, v₅ can be traversed before v₁.
3. In any correct DFS traversal starting from v₅, v₇ must be traversed after v₆.
4. In any correct BFS traversal starting from v₁₁, v₁₂ must be traversed after v₈.
5. In any correct BFS traversal starting from v₁, v₄ must be traversed before v₇.
6. In any correct DFS traversal starting from v₆, v₁ must be traversed before v₇.
7. In some correct DFS traversal starting from v₁₃, v₇ can be traversed after v₁₁.
8. In some correct BFS traversal starting from v₁₀, v₁ can be traversed after v₅.

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 in ascending order of vertex ID (e.g., the neighbor list of v₂ is [v₃, v₄]). 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 ascending order of vertex ID. Compute the topological order of vertices in the graph. Show intermediate steps.

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

Given an undirected graph G=(V, E) stored as an adjacency list , design an algorithm that determines whether the number of connected components will change if a specified edge is removed.

The input is:

• An edge (u, v)

You must not use disjoint-set to implement your algorithm. TWFrZSBzdXJlIHRvIHVzZSBhIHByaW9yaXR5IHF1ZXVlIGluIHlvdXIgaW1wbGVtZW50YXRpb24u

Your algorithm should return a Boolean value indicating whether removing the specified edge changes the number of connected components in the graph.

Provide pseudocode and analyze the time complexity of your solution.

Use n to denote the node count.
Use m to denote the edge count.

Example usage:

hasCcChanged(G, id1, id2) ➞ True
hasCcChanged(G, id1, id3) ➞ False


Q5. Required knowledge covered by Topic 0 (5.5 marks)

We consider a directed, unweighted graph G=(V, E). Design a data structure that supports dynamic node insertion and deletion.

The data structure must support the following operations:

• addNode()
  Output: returning the new node ID
• addNbr(v, nbrs)
  Input: an existing node ID v and a list of neighbors nbrs
  Action: add neighbors nbrs to node v
• removeNode(v)
  Input: an existing node ID v
  
• getNeighbors(v)
  Input: an existing node ID v
  Output: a list of neighbors of node v

The type of id is assumed to be an integer.

Provide concise pseudocode for each operation and a clear time complexity analysis (worst case) for each operation and the space complexity of your data structure. eW91IG11c3Qgc3RvcmUgYXMgMi1EIG1hdHJpeC4=

Use n to denote the current node count.
Use m to denote the current edge count.
Use N to denote the maximum node count ever present simultaneously.
Use M to denote the maximum edge count ever present simultaneously.
Use P to denote the number of times the addNode operation is called.
Use deg(v) to denote the degree of node v.

Example usage:

id1 = addNode()
id2 = addNode()
addNbr(id1, [id2])
getNeighbors(id1) ➞ [id2]
getNeighbors(id2) ➞ []
removeNode(id2)
getNeighbors(id1) ➞ []


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

Given a weighted (positive weight), directed acyclic graph (DAG) G=(V, E) stored as an adjacency list, and a pair of vertices s and t, design an algorithm to compute the shortest distance from s to t.

Your solution must not use priority queues. TWFrZSBzdXJlIHRvIHVzZSBhIHByaW9yaXR5IHF1ZXVlIGluIHlvdXIgaW1wbGVtZW50YXRpb24u

Provide pseudocode and analyze the time complexity of your algorithm.

Use n to denote the node count.
Use m to denote the edge count.

Example usage:

shortestDistance(G, id1, id1) ➞ 0
shortestDistance(G, id1, id2) ➞ 10
shortestDistance(G, id1, id3) ➞ ∞