CS6515 ACTUAL FINAL PAPER 2025 QUESTIONS WITH
ANSWERS GUARANTEE A+
✔✔DFS Algorithm - ✔✔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 - ✔✔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 - ✔✔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 - ✔✔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 - ✔✔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.
, How it works: Starts at a vertex and adds the smallest connecting edge to unvisited
node.
✔✔Ford Fulkerson Algorithm - ✔✔Runtime: O(mC)
Input: Graph with integer edge weights. (Note: Does not work with Infinity)
Output: max flow f*
✔✔Edmonds-Karp Algorithm - ✔✔Runtime: O(nm^2)
Input: Graph with integer edge weights. (Note: Works with Infinity!)
Output: max flow f*
✔✔Orlin Max Flow Algorithm - ✔✔- Current best solution to max flow problem
- Run Time: O(mn)
✔✔Augmenting Path - ✔✔A path that exists on the residual graph from s -> t.
This type of path implies there exists more flow that can be pushed through the graph.
This occurs when there exists a path through which the minimum residual capacity F
among all edges in the path is greater than 0.
✔✔When is a flow a max flow - ✔✔When there is no augmenting path in the residual
graph
✔✔Size(flow) = - ✔✔F_out(L) - f_in(L)
✔✔How to construct a min cut - ✔✔- construct a max flow
- set L to be those vertices reachable from s in the residual graph
- This st cut then has a capacity equal to the max flow
- maxflow = mincut
✔✔Ford-Fulkerson vs Edmonds-Karp - ✔✔FF:
- Finds augmenting paths using DFS or BFS
- O(mC) time, where C is the size of the max flow
- assumes integer capacities
- capacities cannot be infinity
EK:
- Finds augmenting paths using BFS (is an example of FF)
- O(nm^2)
- No assumptions on integer capacities
- Only requires positive capacities
✔✔Edmonds-Karp Number of rounds is at most - ✔✔- mn
- Every round residual graph changes by > 1 edge
ANSWERS GUARANTEE A+
✔✔DFS Algorithm - ✔✔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 - ✔✔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 - ✔✔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 - ✔✔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 - ✔✔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.
, How it works: Starts at a vertex and adds the smallest connecting edge to unvisited
node.
✔✔Ford Fulkerson Algorithm - ✔✔Runtime: O(mC)
Input: Graph with integer edge weights. (Note: Does not work with Infinity)
Output: max flow f*
✔✔Edmonds-Karp Algorithm - ✔✔Runtime: O(nm^2)
Input: Graph with integer edge weights. (Note: Works with Infinity!)
Output: max flow f*
✔✔Orlin Max Flow Algorithm - ✔✔- Current best solution to max flow problem
- Run Time: O(mn)
✔✔Augmenting Path - ✔✔A path that exists on the residual graph from s -> t.
This type of path implies there exists more flow that can be pushed through the graph.
This occurs when there exists a path through which the minimum residual capacity F
among all edges in the path is greater than 0.
✔✔When is a flow a max flow - ✔✔When there is no augmenting path in the residual
graph
✔✔Size(flow) = - ✔✔F_out(L) - f_in(L)
✔✔How to construct a min cut - ✔✔- construct a max flow
- set L to be those vertices reachable from s in the residual graph
- This st cut then has a capacity equal to the max flow
- maxflow = mincut
✔✔Ford-Fulkerson vs Edmonds-Karp - ✔✔FF:
- Finds augmenting paths using DFS or BFS
- O(mC) time, where C is the size of the max flow
- assumes integer capacities
- capacities cannot be infinity
EK:
- Finds augmenting paths using BFS (is an example of FF)
- O(nm^2)
- No assumptions on integer capacities
- Only requires positive capacities
✔✔Edmonds-Karp Number of rounds is at most - ✔✔- mn
- Every round residual graph changes by > 1 edge
