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