CS-6515 EXAM 2 QUESTIONS & ANSWERS
What does the DFS Algorithm do? - Answer -Identify connected components using any
graph.
What is the runtime of the DFS Algorithm? - Answer -O(|V| + |E|)
What does the DFS Algorithm output? - Answer -ccnum array, pre and post order
number arrays, and topological sort on the graph
What does the BFS Algorithm do? - Answer -Identify shortest edge path using any
graph, from a specific start vertex to any reachable vertex.
What is the runtime complexity of BFS Algorithm? - Answer -O(|V| + |E|)
What does the BFS Algorithm output? - Answer -Distance array and previous array for
determining the shortest path.
What does Dijkstra's algorithm do? - Answer -Shortest path between given source
vertex and all other vertices in weighted graph. Weights must be positive.
What is the runtime for Dijsktras algorithm? - Answer -O(|V| + |E| log |V|)
What does Dijkstras algorithm output? - Answer -distance array and previous array for
determining the shortest path
What problem does the Bellman-Ford Algorithm solve? - Answer -Finding the shortest
path between a given source vertex and all other vertices in a weighted graph with
positive or negative weights.
What is the runtime of the Bellman-Ford Algorithm? - Answer -O(|V| * |E|)
What problem does the Floyd-Warshall Algorithm solve? - Answer -Shortest path
between all vertices within a graph. Weights can be positive or negative.
What is the runtime complexity of the Floyd-Warshall Algorithm? - Answer -O(|V|^3)
How is the shortest path represented in the output of the Floyd-Warshall Algorithm? -
Answer -Using a 3D array
What does the SCC Algorithm do? - Answer -Identify strongly connected components
within a directed graph.
What is the runtime of the SCC Algorithm? - Answer -O(|V| + |E|)
What does the DFS Algorithm do? - Answer -Identify connected components using any
graph.
What is the runtime of the DFS Algorithm? - Answer -O(|V| + |E|)
What does the DFS Algorithm output? - Answer -ccnum array, pre and post order
number arrays, and topological sort on the graph
What does the BFS Algorithm do? - Answer -Identify shortest edge path using any
graph, from a specific start vertex to any reachable vertex.
What is the runtime complexity of BFS Algorithm? - Answer -O(|V| + |E|)
What does the BFS Algorithm output? - Answer -Distance array and previous array for
determining the shortest path.
What does Dijkstra's algorithm do? - Answer -Shortest path between given source
vertex and all other vertices in weighted graph. Weights must be positive.
What is the runtime for Dijsktras algorithm? - Answer -O(|V| + |E| log |V|)
What does Dijkstras algorithm output? - Answer -distance array and previous array for
determining the shortest path
What problem does the Bellman-Ford Algorithm solve? - Answer -Finding the shortest
path between a given source vertex and all other vertices in a weighted graph with
positive or negative weights.
What is the runtime of the Bellman-Ford Algorithm? - Answer -O(|V| * |E|)
What problem does the Floyd-Warshall Algorithm solve? - Answer -Shortest path
between all vertices within a graph. Weights can be positive or negative.
What is the runtime complexity of the Floyd-Warshall Algorithm? - Answer -O(|V|^3)
How is the shortest path represented in the output of the Floyd-Warshall Algorithm? -
Answer -Using a 3D array
What does the SCC Algorithm do? - Answer -Identify strongly connected components
within a directed graph.
What is the runtime of the SCC Algorithm? - Answer -O(|V| + |E|)
