Exam 2

Question 1

What does V represent?

Answer 1

Set of vertices

Question 2

What does E represent?

Answer 2

Set of edges

Question 3

What does n = |V| represent?

Answer 3

Number of vertices

Question 4

What does m = |E| represent?

Answer 4

Number of edges

Question 5

What does s represent?

Answer 5

The source vertex

Question 6

What does t represent?

Answer 6

The sink vertex

Question 7

What is Breadth-first Search (BFS) algorithm used for?

Answer 7

To find unweighted Single Source Shortest Path (SSSP), the distance from s to u if s can reach u, otherwise it is infinity; Runtime is O(n+m)

Question 8

What is Dijkstra’s algorithm used for?

Answer 8

To find weighted Single Source Shortest Path (SSSP), the distance from s to u if s can reach u, otherwise it is infinity; Understand that when weights are involved, the runtime increases to O((n+m) log n)

Question 9

What is Depth-first Search (DFS) algorithm used for?

Answer 9

It behaves differently for directed and undirected graphs; In a directed graph, the pre/post numbers give information on how a graph COULD be explored; In an undirected graph, the pre/post numbers give information on how a graph WOULD be explored given a starting point; Runtime is O(n+m)

Question 10

What is the Explore algorithm used for?

Answer 10

This is a subroutine of DFS and does most of the work in DFS, it runs on all edges and vertices that are reachable from the provided v, can be used with a visited array to will set to true for all nodes u that are reachable from v; Runtime is O(n+m) if run by itself

Question 11

What is the Topological Sort algorithm used for?

Answer 11

This algorithm works by running DFS on the DAG (directed acyclic graph - it has no cycles) and using the post order number to sort the vertices from highest post number to lowest post number, when a DAG is ordered from source to sink, then all edges go from left to right; Runtime is O(n+m)

Question 12

What is the Strongly Connected Components (SCC) algorithm used for?

Answer 12

It takes a directed graph and runs DFS twice, running once with pre/post order numbering on the reverse graph of G and sorting V in descending post order numbers, giving sink to source; It then runs again on G with V sorted, the output will have ccnum representing each SCC with highest = source, and lowest = sink, the ccnum can be used to gather up vertices that belong to each SCC; Runtime is O(n+m)

Question 13

What is Kruskal’s Minimum Spanning Tree (MST) algorithm use for?

Answer 13

The algorithm sorts edges by weight of a connected and undirected graph, G = (V,E), and weights w, it grabs the lightest available edge that will not create a cycle when added to the MST, another way to look at this is to never add edges of vertices in the same component in the MST, this continues until all edges that will not create a cycle are added, this happens at exactly n-1 edges; Runtime is O(m log n)

Question 14

What is a source vertex?

Answer 14

It has no incoming edges and has the highest post number

Question 15

What is a sink vertex?

Answer 15

It has no outgoing edges and has the lowest post number

Question 16

Vertices are strongly connected if?

Answer 16

There is a path from v -> w and w -> v

Question 17

In Conjunctive Normal Form (CNF), AND is represented by?

Answer 17

^ looks like an A

Question 18

In Conjunctive Normal Form (CNF), OR is represented by?

Answer 18

V looks like a V

Question 19

What inputs are taken to a max-flow algorithm?

Answer 19

G(V,E), s, t, c where s a source vertex, t is a sink vertex, and c is capacities; This set of inputs is also known as a Flow Network

Question 20

What are the steps involved in obtaining the max-flow of a graph?

Answer 20

Build a residual network of the graph that shows the capacities along edges; Check for any path in the residual network from s to t using DFS or BFS - if none is found, we’re done; If found, get the minimum capacity along the path; Augment the path by capacitive units along the path, forward edges are increased and backwards edges are decreased; Runtime is O(n+m)

Question 21

Describe the Ford-Fulkerson algorithm.

Answer 21

Assumes all capacities are positive integers, runs in rounds by increasing the flow >= 1 per round so there are C rounds where C is the size of max flow; Runtime is O(mC)

Question 22

Describe the Edmonds-Karp algorithm.

Answer 22

Very similar to Ford-Fulkerson except it uses BFS to determine the shortest path rather than “any path”; Runtime is O(nm^2)

Question 23

Does an MST contain cycles?

Answer 23

No, they are acyclic graphs (no cycles)

Question 24

What does the max flow - min-cut theorem state?

Answer 24

The size of the max flow equals the size of the minimum st-cut