cs2010_AY1314S1_Q2

[0WN463]

A few things (6 marks) For these six sub-questions, you are not allowed to use any additional data structure. What is the tightest time complexity of DFS if it is run from a source vertex v of a graph G, if:

3. This graph G is a general graph and is stored in an Adjacency Matrix: .
4. This graph G is a tree and is stored in an Adjacency Matrix: .
5. This graph G is a general graph and is stored in an Edge List: .

6. This graph G is a tree and is stored in an Edge List: .

   3. O(V+E) DFS iterates each vertex once and each edge once. So O(V+E), but to find the edge, we need to iterate through the matrix of size V each time we are at a vertex, and we go to each vertex V times, so it should be O(V^2).
   4. O(V) , Same argument as 3
   5. O((V+E)LogE) Technically, we can convert EL to AL in O(V+E), then the complexity will be bounded as above
   6. O(VLogV)

(4 marks) What is the best algorithm (write down the name and it’s default time complexity) to find the shortest paths from source s to the other vertices in the graph if the graph is:

2. directed, unweighted: .

3. undirected, weighted, and may have negative weight cycle:

   2. Modified Djikstra's O(ELogV) Unweighted, BFS should do right?

   3. ??? Bellman should be needed. All edge just becomes double edge

The original Dijkstra’s algorithm (verbatim, as outlined in Lecture 09) can be used to detect the presence of negative weight cycle.

1. False. Greedy algorithm. Will go on forever. Technically, Dj should terminate, but give WA. Mod Dj is the one that goes forever

2. There is no input graph that can make Bellman Ford’s algorithm runs slower than O(V E). PS: The input graph has to be a simple graph without self-loop or multiple edges.

3. Confused by the Question. BF Killer considered O(VE)? BF killer runs the max total of O(VE) which is its worse case right? BF runs O(kE), where k is the number of loops it runs

[Psyf]

"5. O((V+E)LogE) Technically, we can convert EL to AL in O(V+E), then the complexity will be bounded as above" We aren't allowed to use additional data structures, sadly.

But they said no additional data struct. My reasoning was that you'd have to do O(V+E) anyway because of traversal. But then finding each edge would have you binary search for each query, so multiply by logV. What do you think?

"4. undirected, weighted, and may have negative weight cycle:" But it'll produce WA. That's the problem. What do you think?

"There is no input graph that can make Bellman Ford’s algorithm runs slower than O(V E). PS: The input graph has to be a simple graph without self-loop or multiple edges." Simple graph is assumed throughout the module. I'm not sure about this though. http://people.inf.elte.hu/hytruongson/Bellman-Ford/Bellman-Ford.html This source says BF is O(V^3) for AdjMatrix. I thought it's V^3 because you had to loop through to find the edges? I said O(V^2 + VE) because of V^2 for conversion to AdjList and VE for running BF.

The rest of the issues have been fixed/clarified. Thanks for your contribution :)

[0WN463]

"5. O((V+E)LogE) But they said no additional data struct. My reasoning was that you'd have to do O(V+E) anyway because of traversal. But then finding each edge would have you binary search for each query, so multiply by logV. What do you think?

Hmm if that's the case, we would go to each vertex once, and at each vertex, we binary search for the source. So O(V log E). Once we found the source in the EL (assuming we sorted the EL by sources), we can just iterate through from that point onwards to get its neighbours. We would iterate all E edges once, so it should be O(V log E + E)?

4. undirected, weighted, and may have negative weight cycle: But it'll produce WA. That's the problem. What do you think?

Why would it be WA though? If it is undirected, the same (non-negative) edge will not be re-relaxed as if it is, the distance will increase, not decrease. Or are you talking about the negative cycle? If that's the case, then the idea of a shortest path is ill-defined. It's kinda like asking a longest path when there is a cycle.

"There is no input graph that can make Bellman Ford’s algorithm runs slower than O(V E). PS: The input graph has to be a simple graph without self-loop or multiple edges." Oh so you meant bad inputs. Well, we can always say the input is padded with M = 10^100 characters of rubbish each time to make it not O(VE), but I guess it's up to Halim to clarify