Cs6515 Exam 2 2026/2027 Actual Questions With Verified Answers.

CS6515 EXAM 2 2026/2027
ACTUAL QUESTIONS WITH
VERIFIED ANSWERS.

BFS Algorithm - correct answer -Input: Directed or Undirected
Graph G, and start vertex s


Output:
1. dist[u] - distance from s to u if s can reach u, inf otherwise
2. prev[z] - the parent index of vertex z


Runtime: O(m+n)


- Use this for unweighted Single Source Shortest Path
- Dist is given as the number of edges from s to u, not the sum of
weights




DFS Algorithm - correct answer -Input: Graph G


Output:
1. prev[z] - parent index of vertex z

,2. pre[z] - pre number of vertex z
3. post[z] - post number of vertex z
4. ccnum[z] - connected component number of z


Runtime: O(m+n)




Dijkstra's Algorithm - correct answer -Input: Graph (directed/un-
directed), Start vertex.


Output:
1. dist[u] - distance from s to u if s can reach u
2. prev[z] - parent index of vertex z


Runtime: O( (n + m) * log(n) )


More sophisticated BFS that utilizes miniheap data structure.
Such requires an additional log(n) time over BFS because of this




SCC Algorithm - correct answer -Input: Directed Graph


Output:
1. Metagraph of G.

, 2. Connected Component Numbers for each vertex (this comes
from DFS, explained above)


Runtime: O(n + m)




Kruskal Algorithm - correct answer -Input: connected undirected
graph G, edge weights w


Output: minimum spanning tree defined by the edges


Runtime: O(m log(m)) or O(m log(n))
Input: Connected, undirected graph. (Must have edge weights...
basis of algo)




How it works: Basically Sorts edges from least to greatest and
starts building the tree.




Prim's Algorithm - correct answer -Runtime: O(m log(m)) or O(m
log(n))
Input: Connected, undirected graph. (Must have edge weights...
basis of algo)
Output: The Minimum Spanning Tree of the graph.