unit 3 AOS 2

Question 1

Limitations of prims

Answer 1

Limitation: cannot work for disconnected node and prims (by default) assumes all edges are undirected unless modified

Question 2

Limitation and runtime of Dijksta’s

best + worse case

Answer 2

• Does not reconsider nodes that has already been visited
• does not consider negative loops

MAY not work with negative cycles

WORSE: O(V^2) [for single source shortest path]
Best: O(1)

Question 3

Bellman-Ford

runtime and facts

Answer 3

• Each iteration has to go through every edge
• Bellman-Ford iterates through all the edges (NOT NODES)
• runs |v|-1 times (unless uses naiive implmentation)

O(V E)

Question 4

Floyd-Warshall’s

runtime and facs

Answer 4

Floyd-Warshall iterates through all the nodes

O(n^3)

Question 5

Pagerank formula

Answer 5

(1-d)/n
+
d(links incoming/links outgoing)

only add if links are incoming to the node

Question 6

Runtime of DFS

Answer 6

O(V+E)