CS6515 - EXAM 2 UPDATED ACTUAL QUESTIONS AND CORRECT ANSWERS

CS6515 - EXAM 2 UPDATED ACTUAL QUESTIONS AND
CORRECT ANSWERS

Question:
1. How to get connected components in undirected graph?
Answer:
Run DFS and keep track of component number

Question:
2. How do we get the connected components in an undirected graph? What's the runtime?
Answer:
DFS
Runtime(n+m), n = |v|, m = |E|
ccnum[v] will tell you which connected component the vertex v belongs to. Vertices that have the same
ccnum are part of the same connected component.
Initialize cc = 0 Initialize an empty set or list visited Initialize an empty array ccnum
for each vertex v in V: set visited(v) = FALSE set ccnum(v) = 0 for each vertex v in V: if not visited(v): cc
= cc + 1 Explore(v)
Explore(z): set ccnum(z) = cc set visited(z) = TRUE for each edge (z, w) in E: if not visited(w):
Explore(w)

Question:
3. DFS algorithm to find a path between connected vertices in an undirected graph
Answer:
Initialize cc = 0 Initialize an empty set or list visited Initialize an empty array ccnum Initialize an empty
array prev
for each vertex v in V: set visited(v) = FALSE set ccnum(v) = 0 set prev(v) = NULL
for each vertex v in V: if not visited(v): cc = cc + 1 Explore(v)
Explore(z): set ccnum(z) = cc set visited(z) = TRUE for each edge (z, w) in E: if not visited(w):
Explore(w) set prev(w) = z
Path is reconstructed from v (target) back to u (source) by backtracking through the prev array

Question:
4. How do we get the connected components in a directed graph? What's the runtime?
Answer:
1. Run depth-first search on GR.
2. Run the undirected connected components algorithm (from Section 3.2.3) on G, and during the
depth-first search, process the vertices in decreasing order of their post-order numbers from step 1.
Runtime(n+m), n = |v|, m = |E|

Question:
5. Types of edges and their post-order number direction
Answer:
Tree edge: post(z) > post(w) Back: post(z) < post(w) Forward: post(z) > post(w) Cross: post(z) > post(w)

,Question:
6. Cycles
Answer:
G has a cycle if and only if its DFS tree has a back edge

Question:
7. Topologically (linearly) sorting a DAG
Answer:
One run of DFS and then sort by decreasing post-order number
Usually used on an SCC metagraph to get information about the relationships
First SCC is a source and last SCC is a sink but may not be the only ones
O(n+m)

Question:
8. Source vertex
Answer:
- No incoming edges = highest post order # in DAG. Always at least one

Question:
9. Sink vertex
Answer:
- No outgoing edges = lowest post order # in DAG. Always at least one

Question:
10. Alternative topological sorting algorithm
Answer:
1. Find a sink, output it, and delete it
2. Repeat 1 until the graph is empty

Question:
11. Strongly connected components
Answer:
Vertices v and w are strongly connected if there is a path from v to w and w to v. In undirected graphs =
max set of connected vertices In directed graphs = max set of strongly connected vertices

Question:
12. metagraph on Strongly Connected Components
Answer:
Simplified representation of the original directed graph. In this metagraph, each node represents a strongly
connected component of the original graph, and there is a directed edge between two nodes in the
metagraph if there is a directed edge between any vertex in the corresponding SCCs in the original graph.
Each is a DAG. Every directed graph is a DAG of its SCCs

Question:
13. For all directed graphs, does the vertex with the highest post order number always lie in a source SCC?
Answer:
Yes, for every DFS run.

, Question:
14. SCC algorithm time complexity
Answer:
O(V + E)

Question:
15. SCC algorithm
Answer:
Kosaraju's Algorithm to Find SCCs: Step 1 - DFS on Original Graph: Perform a DFS on the original graph
to get the post-order of vertices. Store the vertices in a stack based on their post-order. Step 2 - Reverse the
Graph: Reverse all the edges in the graph. Step 3 - DFS on Reversed Graph: While the stack is not empty,
pop a vertex v: If v has not been visited, perform a DFS starting from v on the reversed graph. All the
vertices visited in this DFS form one Strongly Connected Component. Mark them as visited and assign
them the same component ID.




Question:
16. BFS
Answer:
O(n+m)
input: G = (V, E) and start vertex
output: for all v v in V, dist(v) = min number of edges from s to v. inf if no path. prev(v)

Question:
17. Dijkstra's algorithm
Answer:
Considers edge weights to find the shortest path. Does not work with negative edge weights.
O((n+m)logn) input: G = (V, E), source vertex, and l(e)>0 for every edge
output: for all vertices, dist(v)=length of the shortest s -> v path in G
uses min-heap

Question:
18. Boolean clause
Answer:
An OR of several literals

Question:
19. Conjunctive normal form (CNF)