Input/Output/Variables Accessed

Question 1

DFS: What is the input, output, and variables we have access to?

Answer 1

Input: G = (V, E) Output:* A topological sort on a DAG* undirected graph: ccnum (connected component number)* directed graph: a list of connected componentsAccess to:* prev array* pre array* post array

Question 2

Explore: What is the input, output, and variables we have access to?

Answer 2

Input:* G = (V, E)* Start vertex v in VOutput:* visited(u) - visited array which is set to TRUE for all vertices reachable from vAccess to:* ccnum array (ccnum[])* previously visited array (visited[]) * An array of vertices before a given vertex. * Used by Explore and required for DFS.

Question 3

BFS: What is the input, output, and variables we have access to?

Answer 3

Input:* G = (V, E)* Start vertex v in VOutput:* dist[] - for all vertices u reachable from the starting vertex v, dist[u] is the shortest path distance from v to u. If no such path exists, infinity otherwise.Access to:* prev[] - vertex preceding u in shortest path from v to reachable vertex u

Question 4

Djikstra’s: What is the input, output, and variables we have access to?

Answer 4

Input:* G = (V, E)* Start vertex v in VOutput:* dist[] - for all vertices u reachable from the starting vertex v, dist[u] is the shortest path distance from v to u. If no such path exists, infinity otherwise.Access to:* prev[] - vertex preceding u in shortest path from v to reachable vertex u

Question 5

Bellman Ford: What is the input, output, and variables we have access to?

Answer 5

Input:* G = (V, E)* Start vertex v in VOutput:* The shortest path from vertex s to all other vertices.Access to:* Detect negative weight cycles. We can compare T[n, *] to T[n - 1, *]. * We can only find negative weight cycles that can be reached from starting vertex s.

Question 6

Floyd-Warshall: What is the input, output, and variables we have access to?

Answer 6

Input:* G = (V, E)Output:* The shortest path from all vertices to all other verticesAccess to:* We can detect negative weight cycles by checking the diagonals (T[n, i, i]).

Question 7

SCC: What is the input, output, and variables we have access to?

Answer 7

Input:* G = (V, E)Output:* meta-graph (DAG) that contains the connected components* Topological sorting of the meta-graph * With a source SCC first and a sink SCC lastAccess to:* ccnum[] - strongly connected components produced from the 1st DFS run

Question 8

Kruskal’s: What is the input, output, and variables we have access to?

Answer 8

Input:* Connected, Undirected Graph G = (V, E) with edge weights w_eOutput:* An MST defined by the edges E

Question 9

Prim: What is the input, output, and variables we have access to?

Answer 9

Input:* Connected, Undirected Graph G = (V, E) with edge weights w_eOutput:* An MST defined by the prev[] array

Question 10

2-SAT: What is the input, output, and variables we have access to?

Answer 10

Input:* A Boolean formula in 2-CNF is represented as a set of clauses where each clause is a disjunction of exactly two literals.Output:* A Boolean value indicates whether the given 2-CNF formula is satisfiable. If it is satisfiable, the algorithm may also provide a satisfying assignment of variables.

Question 11

Ford-Fulkerson: What is the input, output, and variables we have access to?

Answer 11

Input:* G = (V, E)* Flow capacity c* Source node s* Sink node tOutput:* Max FlowAccess to:* Can trivially create the final residual network with G* Max flow of G

Question 12

Edmonds-Karp: What is the input, output, and variables we have access to?

Answer 12

Input:* G = (V, E)* Flow capacity c* Source node s* Sink node tOutput:* Max FlowAccess to:* Can trivially create the final residual network with G* Max flow of G