Question

Answer True or False

1. For graph representation, adjacency Matrix is more efficiency than adjacency list in term of searching for edge.

2. Topological sort runs in O(|V| + |E|) where |V| is the number of vertices, and |E| is the number of edges in the input graph.

3. If vertex u can reach vertex v, and vertex v can reach vertex u, then vertices u and v are in the same Strongly-connected component (SCC).

4. The Bellman-Ford algorithm will run forever if the input graph has negative weights on the edges.

5. For a graph with only positive edge weights, Dijkstra's algorithm solves the single-source shortest path (SSSP) problem faster than Bellman-Ford on a graph.

6. Dynamic programming depends on the input problem having an optimal substructure.

7. The longest-common subsequence problem on strings of length n and m can be solved in time O(nm).

8. The adjacency matrix’s space complexity is O(|V|+|E|), for a graph G = .

9. Given any two strings S1 and S2, there is only one longest common subsequence (that is, the LCS is unique).

10. Depth-First Search runs in O(|V| + |E|) where |V| is the number of vertices, and |E| is the number of edges in the input graph.

Breadth-First Search finds the shortest distance --- in terms of the number of hops --- from source vertex to each other reachable vertex in a graph.

Kruskal's algorithm is a greedy algorithm.

For any graph G with positive edge weights, there is only 1 minimum-spanning-tree (MST) for G.

The time complexity of rod-cutting problem is Θ(n2)

2^(n+1)= O(2^n)

Answer 1

1.For graph representation, adjacency Matrix is more efficiency than adjacency list in term of searching for edge.

Ans:True

2.Topological sort runs in O(|V| + |E|) where |V| is the number of vertices, and |E| is the number of edges in the input graph.

Ans:True

3.If vertex u can reach vertex v, and vertex v can reach vertex u, then vertices u and v are in the same Strongly-connected component (SCC).

Ans:True

4.The Bellman-Ford algorithm will run forever if the input graph has negative weights on the edges.

Ans:True

5.For a graph with only positive edge weights, Dijkstra's algorithm solves the single-source shortest path (SSSP) problem faster than Bellman-Ford on a graph.

Ans:False

6. Dynamic programming depends on the input problem having an optimal substructure.

Ans:True

7.The longest-common subsequence problem on strings of length n and m can be solved in time O(nm).

Ans:False

Explanation:Time complexity of the above longest-common subsequence problem is O(2^n)

8.The adjacency matrix’s space complexity is O(|V|+|E|), for a graph G

Ans:True

9.Given any two strings S1 and S2, there is only one longest common subsequence (that is, the LCS is unique).

Ans:False

Explanation:Not always the longest common subsequence is unique, sometimes there can be multiple longest common subsequences of equal length.

10.Depth-First Search runs in O(|V| + |E|) where |V| is the number of vertices, and |E| is the number of edges in the input graph.

Ans:True

11.Breadth-First Search finds the shortest distance --- in terms of the number of hops --- from source vertex to each other reachable vertex in a graph.

Ans:True

12.Kruskal's algorithm is a greedy algorithm.

Ans:True

Explanation:It is a greedy algorithm in graph theory as in each step it adds the next lowest-weight edge that will not form a cycle to the minimum spanning forest.

13.For any graph G with positive edge weights, there is only 1 minimum-spanning-tree (MST) for G.

Ans:False

Explanation: If each edge has a distinct weight then there will be only one, unique minimum spanning tree.

14The time complexity of rod-cutting problem is Θ(n2) 2^(n+1)= O(2^n)

Explanation:Time Complexity depends on the type of programing implementation used in rod-cutting problem.