Exam 2

Question 1

What must be present if there’s a back edge?

Answer 1

There must be a cycle in the graph if the DFS tree has a back edge

Question 2

What is a DAG and what are its characteristics?

Answer 2

directed acyclic graphs

every vertex u where there is an edge to vertex v has one direction

has no cycles in the graph

Can be topologically sorted

Must have one or more source vertex

Must have one or more sink vertex

Question 3

What is an alternative topological sorting algorithm?

Answer 3

Alternative topological sorting:
Find a sink vertex, output it, and then delete
Repeath this first step until the graph is empty

Question 4

How do we find a sink vertex in a DAG?

Answer 4

Find the lowest postorder number vertex in a DAG

Question 5

What is the pseudocode for the SCC algorithm?

Answer 5

• construct a reverse G of the original input graph G
• run DFS on G reverse
• order V by decreasing post order number
• run undirected connected components alg on G

Question 6

What are the types of edges in a graph?

Answer 6

forward edge - is a forward edge if it points from a vertex to one of its descendants in the DFS tree, but is not a tree edge
- pre(u) < pre(v)
- post(u) > post(v)
-

back edge - an edge u-v is a back edge if it points from a vertex to one of its ancestors in the DFS tree
- creates a cycle in the DFS tree
- pre(u) > pre(v)
- post(v) > post(u) (only one where this is the case)

tree edge - edge u-v is a tree edge if v is a direct descendent of u in a DFS tree
- part of the DFS tree
- pre(u) < pre(v)

cross edge - edge u-v is a cross edge if it connects two vertices that are neither in a direct ancestor-descendant relationship nor part of the same DFS tree
- pre(u) and pre(v) have no distinct relationship
- the finish time of u and v also have no distinctive relationship
-

Question 7

How do you find connected components in an undirected graph G? What is the runtime for doing this? What is the pseudocode?

Answer 7

Run DFS and keep track of component numbers #

O(n+m)

Psuedocode:
- Running explore from vertex
- Store z as visited because its the first time visiting
- Also store z in the current count for the connected components
- Now explore neighbors of z
If w or neighbor hasn’t been visited, the we call explore on that neighbor (recursively)

Question 8

How can we use DFS to find a path between 2 vertices?

Answer 8

Run DFS and populate the previous values for each vertex in a previous array

We then have the previous array and use this to find a path between the pair of connected vertices

Question 9

How do we find connectivity info on a directed graph?

Answer 9

We run DFS on the directed graph and add pre/post order numbers

Specifically:
We use clock values to track the pre and post orders

When first visiting vertex z, we store the preorder number

After visiting / exploring vertex z, we store the postorder number

Question 10

What is required for there to be a cycle in a DFS tree?

Answer 10

There must be a back edge

Question 11

Does a DAG have cycles or back edges

Answer 11

No cycles, no back edges

Question 12

What happens when we topologically sort a DAG? Can there be more than one topological orderings?

Answer 12

Topological sort -> ordering from vertices from lower numbers to higher numbers

All edges should go from higher postorder number to lower postorder number

Thus, we order vertices by decreasing post order number

All post order numbers range between 1 and 2n

Therefore, we make an array of size 2n and insert each vertex in to the array in the appropriate place based on their post order number. We then iterate from highest to smallest and output the vertices. This step takes linear time

Yes, there can be more than one topological orderings

Question 13

What are the source and sink vertices? How many do a DAG have?

Answer 13

Source = no incoming vertices; highest post order #

Sink = no outgoing edges; lowest post order #

Every DAG has one or more sink vertices

Question 14

Vertices u and v are strongly connected if …

Answer 14

and only if there is a path u to v and v to u

Question 15

How are SCC’s for an undirected graph found?

Answer 15

We find the SCC components in topological order

We visit any vertex from the sink vertex and visit nothing else
Then we find the strongly connected component

This even works for vertices like A where there are no other vertices in the SCC and they reach the whole graph

But once we find a sink vertex, we can run explore and get all parts of the SCC

Question 16

What does BFS do? What is it’s runtime?

Answer 16

BFS explores graph in layers
- Specify start vertex as an input
- Returns the distance of every vertex from the start vertex
- O(n+m)

Question 17

What does Dijkstra’s algorithm do? What is it’s runtime?

Answer 17

Dijkstra’ algorithm:
- More sophisticated version of BFS
= We are given a weights/length for every edge (needs to be positive)
- Output: shortest path from S to V
- Uses min-heap
- Runtime: O((n + m) * log n)

Question 18

What is the general SCC algorithm? What does it do and what is it’s runtime?

Answer 18

input: directed graph G in adj list

Steps:
- construct a reverse graph Gr
- run DFS on the reverse graph Gr
- order the vertices by post order number by decreasing post order number
- run undirected connected components algorithm on the graph

Overall runtime: O(n+m)

Question 19

Every directed graph is a …

Answer 19

DAG of its SCC’s

Question 20

What is a satisfiability problem? What is the k-SAT problem? k-SAT is np-complete for all k values?

Answer 20

input: CNF formula with n variables and m clauses

output: assignment (T or F) to the variables satisfying each of the clauses if one exists

For the k-SAT problem:
input: CNF formula with n variables and m clauses (each of size <= k)

output: assignment (T or F) to the variables satisfying each of the clauses if one exists (no if none exists)

The K-sat problem is NP-complete for k >= 3

Question 21

Solve this satisfiability problem:
(x2) ^ (xbar3 v x4) ^ (x3 v xbar5 v xbar1 v x2) ^ (xbar2 v xbar1)

Answer 21

Answer:
X1 = F
X2 = T
X3 = F

Question 22

How can an input to the satisfiability problem be simplified?

Answer 22

Simplify:
- take any unit clause with 1 literal:
- satisfy it the single literal
- remove clauses containing that same literal and drop the bar of the literal (opossite)
- let f’ be the resulting formula

Thus, f formula input is satisfiable if f’ is satisfiable

Can assume this for all cases where size = 2

Question 23

How is a graph related to a satisfiability problem? How is an SCC used?

Answer 23

Directed graphs to map out the implications for setting a given value to T or F indicating what you must set the next var to T or F

ex)
Take f with all clauses of size 2 with n variables and m clauses

2n vertices corresponding to the variables
2m edges corresponding to 2 “implications” per clause

If a literal var and its negation are in the same SCC, then f is not satisfiable

Its also true that any literal and its negation are in different SCCs, then there is a satisfying assignment

Question 24

What is the algorithm for the satisfiability problem? Pseudocode? Runtime?

Answer 24

2-SAT problem (for k = 2)

Based on:
- if for all i, if xi and xbari are in different SCC
then S is a sink SCC <=> Sbar is a source SCC

Algorithm:
- construct a graph G for f
- Take a sink SCC S
- set S=T (and Sbar = F)
- remove S and Sbar
- repeat until empty

O(n + m) runtime

Question 25

What is the MST problem? What are 2 algorithms for solving the MST problem?

Answer 25

input: given an undirected graph with weights

output: find the minimal size connected subgraph
- or minimum spanning tree of minimum weight

Both Kruskal’s algorithm works and Prim’s algorithm works for MST

Question 26

What are the properties of a tree?

Answer 26

n vertices, n-1 edges

exactly one path between every pair of vertices

Any connected graph G (V,E) with |E| = |V| - 1
is a tree

Question 27

How does Kruskal’s algorithm work? pseudocode/steps, runtime

Answer 27

input: undirected graph G (V,E) with weights

• sort each edge E by increasing weight (merge sort)
• set x != 0
• for each edge in the graph (in order):
  • if x U e does not have a cycle:
    x = x U E

return x

Total runtime: O(m log n )

Question 28

What are cuts and what is the cut property? What algorithm takes advantage of the cut property?

Answer 28

Cuts are edges where one point is in S and the other is in S bar - they are the edges crossing between S and S bar

for any undirected graph:
you partition portions of the graph as S and Sbar

cut(S, Sbar) = edge crossing from S to Sbar

The cut property:

We are building a partial solution X we are building up

The green edges part of the MST T

We take subset S and look at cut between S and S bar

At of all the cut edges between S and S bar in purple, I want to find the minimum weight edge - this is e star

Any edge that’s a minimum across a cut is going to be part of some MST

Prim’s algorithm and Kruskal’s algorithm uses the cut property
Kruskal’s Algorithm: Considers edges in increasing order and uses the cut property to decide if an edge should be added to the MST.

Prim’s Algorithm: Grows the MST by adding the smallest edge crossing the cut that separates the MST from the rest of the graph

Question 29

What is the max-flow problem?

Answer 29

Input: directed graph G (V,E) with s and t input vertices and capacities for each edge

Output: find the max flow for each edge where the capacity constraint is met and conservation of the flow is maintained (flow into v = flow out of v)

Fe is set for each edge in the input graph

Capacity Constraint: we need to have fe less than ce

Conservation of flow constraint: for all vertices minus s to t:
Flow in to v must be conserved or must equal the flow out of v

Flow into v:
Sum of the edges over w to v of the flow along this edge

Flow out of v:
Sum of the edges v to z of the flow along that edge

We are to find the valid flow of maximum size

Question 30

Is it okay to have a cycle in the graph for a max-flow problem?

Answer 30

Yes

Question 31

How do anti-parallel edges come into play in the max flow problem?

Answer 31

Simplification of the input network

We add edge capacities and now we find an equivalent flow network and the new network should not have anti parallel edges

We split the path from b to a into a 2 part path - b to f and f to a

Question 32

What is the Ford-Fulkerson algorithm, runtime, and steps/pseudocode?

Answer 32

Steps:
Considering the residual network we build it first
We look for path from s to t
If there’s no path, then output f
If we find the path, we donate it as p
Given p, the min capacity along p is Gf is c(p)
We augment the current flow by c(p) units along P
We repeat from step 2 until no such st-path

Runtime: O(mc)

Question 33

How does the Edmonds-Karp algorithm work? Runtime? Steps/pseudocode?

Answer 33

It uses Breadth-First Search (BFS) to find the shortest augmenting paths in terms of the number of edges. This guarantees that the algorithm runs in polynomial time

Steps:
- Construct the residual graph Gf based on the original capacities and current flows. Initially, it is the same as the original graph with capacities c(e)
- find the augmenting graph using BFS
- Update the flows in the following steps:
- determine the residual capacity of the augmenting graph
- increase the flow along the path P - for each edge in the path:
- update the flow by adding f(u,v)

f(u,v)=f(u,v)+cf (P)

cf(u,v)=c(u,v)−f(u,v)

Also update the reverse flow f(v, u) and the reverse residual capacity cf(v,u)

f(v,u)=f(v,u)−cf(P)

cf(v,u)=c(v,u)−f(v,u)

Repeat the process until no more augmenting paths can be found from s to t in the residual graph.

Runtime: O(VE^2) or O(m^2n)

Question 34

What is the max-flow / min-s-t cut theorem?

Answer 34

A cut is a partition of the L U R

s-t cut is a cut where S E L, t E R

capacity(L,R) = sum Cvw = capacity from L to R

for any flow f and any S-T cut (L,R)

size f <= capacity(L,R)

max size f <= minimal capacity(L,R)

claim is size(f) = f(out) L - f(in) L

we want a size(f) <= capacity(L,R)
max-flow <= min s-t cut capacity

Question 35

What is the residual network for the Ford Fulkerson algorith?

Answer 35

Residual network Gf

For the flow of flow graph G with edge capacities ce, for each edge in the graph and flow in the graph fe:
- if vw edge in and flow of wv edge are less than the capacity of vw edge, then add vw edge to the residual network graph Gf with capacity cvw - fvw

• if vw edge in and flow of wv edge are greater than 0, then add wv edge to the capacity Gf with capacity fvw

Question 36

What is the main difference between Ford-Fulkerson and Edmond’s-Karp?

Answer 36

• Edmond’s-Karp uses BFS while Ford-Fulkerson uses BFS or DFS or other approaches
• Edmond’s-Karp uses BFS to ensure that the shortest path is found in each iteration. This guarantees that the number of augmenting steps is minimized
• Edmonds-Karp is O(m^2n) while the Ford-Fulkerson time complexity depends on whether DFS or BFS is used (Edmonds-Karp provides a predictable runtime)

Question 37

You are given an unweighted, undirected graph G=(V, E) where V is a list of vertices and E is an adjacency list of edges. You are also given a vertex x and a value k such that you want to avoid x and any vertex within k distance of x. Lastly you are asked to find a shortest path from a given s to t. Assume that there is a path from s to t such that you can avoid x and vertices within k distance of x

Select the algorithm that is considered correct and optimal for this class. What is the runtime?

a.
We first run BFS from x such that we get shortest path costs to all other vertices. We then modify BFS such that if when we would visit a v in V that has a dist ≤ k from x, we avoid it instead of following that path. Run G through the modified BFS from s and return the shortest path from s to t.

b. We first run BFS from x such that we get shortest path costs to all other vertices. We then remove all v in V such that the dist from x is ≤ k. Run the updated G’ through BFS from s and return the shortest path from s to t.

c. dist = BFS(G, x).dist
G’ = G
for v in V:
if dist[v] ≤ k:
G’.remove(v)
prev = BFS(G’, s).prev
path_list = t
v = t
while prev[v] not null:
v = prev[v]
path_list = v + path_list
return path_list

d. Assuming all edges have a cost of 1, we first run Dijkstra’s from x such that we get shortest path costs to all other vertices. From all v in V that has dist to x ≤ k, set edges touching v to a cost of infinite. Run the updated G’ through Dijkstra’s from s and return the shortest path from s to t.

Answer 37

Correct answer b

By modifying the graph to remove any unwanted vertices, we create shortest paths that do not use the vertices we cannot travel through. BFS will find the shortest path for s to t.

runtime: The first BFS has a known runtime of O(n+m). Removing unwanted vertices and its edges is O(n+m). The second BFS is also O(n+m). This gives us a final runtime of O(n+m).