Question

1. True/False:

Mark either T (true) or F (false) for each statement in below. Write in one short sentence why you chose that answer, if necessary. You may lose points if your answer is very long.
a. Adjacency lists are more space efficient than adjacency matrices for sparse graphs. A sparse graph G = (V,E) has |E| = O(|V|).
b. The maximum number of edges in a graph with n vertices is n (n +1) / 2 .
c. A spanning tree of a graph with n vertices contains n edges.
d. Dijkstra’s algorithm does not work on directed graphs.
e. A dynamic programming algorithm makes short-sighted choices that are locally optimal.
f. Dynamic programming is an appropriate choice to solve merge sort.
g. Prim’s and Kruskal’s algorithms are examples of greedy algorithms.
h. In a flow network, the capacity of an edge must be less than or equal to the flow on the edge.
i. Dynamic programming uses memoization to avoid solving the same subproblem more than once.
j. Choice of data structures do not impact the time complexity of graph algorithms.

Answer 1

(a) - True

(b)- False

(c)- False

(d) - False

(e) - False

(f) - False

(g)- True

(h)- False

(i) - False

(j) - False

Step-by-step explanation:

(a)- In an adjacency list the usage of space depends upon the number of edges and vertices in the graph while in the case of the matrix efficiency depends upon the square of the vertices.

(b) The maximum number of edges is n*(n-1).

(c) The number of edges with a spanning tree of n vertices contains n-1 edges.

(d) Dijkstra's Theorem simply refers the adjacent vertices of a vertex and is independent of the fact that a graph is directed or in directed.

(e) Greedy Algorithm makes short sighted choices

(f) Consider the term overlapping sub-problems which is the technique used in Dynamic programming it uses previous calculations to find optimal solutions however in case of merge sort the idea is to break down array into smaller pieces that don't overlap unlike dynamic programming.

(g) Prim and Kruskal's algorithm are examples of greedy algorithm because the use the idea to pick the minimum weight edges at every step which is the approach of a greedy algorithm.

(h) the amount of flow on an edge cannot exceed its capacity.

(i) Dynamic Programming can be implemented using tabulation too.

(j) Different data structures have different time complexity.