cs2010_AY1516S1_Q2.txt

[0WN463]

B.2 Gotta Find ’Em All Challenge (10 marks)

2. 6C3 = 20 ??? But when you choose vertex 0,1,3, it will form a triangle and not span. So I think it should be 6C3 - 4(triangles) = 16?

C.1 Graph Traversal (10 marks)

1. BFS() until layer 8. so O(8(V+E)) = O(8(V+V-1)) which is approximately equal to O(V) How did you get E= V-1? It is a general graph with near complete so shouldn't E be close to V(V-1)/2?

Not sure if this works. But if you look at a complete graph, all nodes are attached to V-1 edges. This means to disconnect a component, we need to remove at least V-1 edges. So we can just check if k >= V-1. Which means we only need to check for V = 6,7,8 as k <=7 And to check, we check if any node has no edges, OR even better, if V-1 "missing" edges are associated to the same node So we store the missing edges as a EL, iterate through it to check if we see V-1 of the same node. So it will be O(k) to iterate and check.

[Psyf]

B.2

2. You are right :o I'm so blind. Committed.

"C.1 Graph Traversal (10 marks) BFS() until layer 8. so O(8(V+E)) = O(8(V+V-1)) which is approximately equal to O(V) How did you get E= V-1? It is a general graph with near complete so shouldn't E be close to V(V-1)/2?" I did a stupid mistake. it should have been O(8(V-1)). Since we look at 8 nodes and their edges (max of V-1 each). I, however, am not sure whether your solution is faster/quicker to type out. Changes made in explanation, thanks for pointing it out.