1. There are no ___ edges in an undirected graph.
- Forward
- Back
- Cross ✔
- Both forward and back
2. Those problems in which Greedy finds good, but not always best is called a greedy
- Algorithm
- Solution
- Heuristic ✔
- Result
3. For an undirected graph, there is no distinction between forward and back edges.
- True ✔
- False
4. Counting money problem:
- can be optimally solved by greedy algorithm ✔
- cannot be optimally solved by greedy algorithm
- cannot be solved by brute force algorithm
- All of the given
5. You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T?
- (V+E) ✔
- V.E
- V
- E
6. Networks are ___ in the sense that it is possible from any location in the network to reach any other location in the digraph.
- complete ✔
- incomplete
- not graphs
- transportation
7. Graph is not a good way to model some sort of “connection” or “relationship” or “interaction” between pairs of objects taken from a set of objects
- True
- False ✔
8. In computing the strongly connected components of a digraph, vertices of the digraph are not partitioned into subsets
- True
- False ✔
9. In general, the Activity Selection Problem is to select a ___
- Minimum -size set of interfering activities
- Maximum-size set of mutually non-interfering activities
- Maximum-size set of interfering activities
- Minimum-size set of mutually non-interfering activities ✔
10. Which is a true statement in the following?
- Kruskal algorithm is a multiple source technique for finding MST
- Kruskal’s algorithm is used to find the minimum spanning tree of a graph, time complexity of this algorithm is O(EV)
- Both of the above ✔
- Kruskal’s algorithm (choose best non-cycle edge) is better than Prim’s (choose best Tree edge) when the graph has relatively few edges.
