CS502 Quiz 4

Q1. Equivalence relation partitions the vertices into _________ classes of mutually reachable vertices and these are the strong components

1. Non equivalence
2. Variance
3. Non classes
4. Equivalence

Correct answer: Equivalence

Q2. In Timestamped DFS-cycles lemma, if edge (u, v) is a back edge, then _________

1. {{f[u]}} {{f[v]}}
2. {{f[u]}} {{f[v]}}
3. {{f[u]}} > {{f[v]}}
4. {{f[u]}} < {{f[v]}}

Correct answer: {{f[u]}} < {{f[v]}}

Q3. For _____________ graphs, there is no distinction between forward and back edges.

1. large
2. directed
3. undirected
4. medium

Correct answer: undirected

Q4. In computing the ____________ components of a digraph, vertices of the digraph are partitioned into subsets.

1. worst
2. best
3. strongly connected
4. weakly connected

Correct answer: strongly connected

Q5. In undirected graph, by convention all the edges are called _________ edges.

1. Both forward and back
2. Back
3. Forward
4. Cross

Correct answer: Both forward and back

Q6. We say that two vertices u and v are mutually _______ if u can reach v and vice versa.

1. Not Reachable
2. Reachable
3. Crossed
4. Forward

Correct answer: Reachable

Q7. In Timestamped DFS, If there is a back edge (u, v) then v is an ancestor of u and by following tree edge from v to u, we get ______________.

1. a line
2. nothing
3. a cycle
4. a graph

Correct answer: a cycle

Q8. The ________ given by DFS allow us to determine whether the graph contains any cycles.

1. Topological sort
2. Time stamps
3. Order
4. BFS traversing

Correct answer: Time stamps

Q9. A topological sort of a DAG is a __________ ordering of the vertices of the DAG such that for each edge (u, v), u appears before v in the ordering.

1. Linear
2. Non-Linear
3. Sequence
4. Parallel

Correct answer: Linear

Q10. If you find yourself in maze the better traversel approach will be :

1. DFS
2. Level order
3. BFS
4. BFS and DFS both are valid

Correct answer: BFS