Multiple Choice Questions (MCQs)
In strong components algorithm, first of all DFS is run for getting ________ times of vertices.
In Dynamic Programming approach, we do not store the solution to each sub-problem in case if it reappears.
If a graph has v vertices and e edges then to obtain a spanning tree we have to delete
Diagraphs are not used in communication and transportation networks.
If there are Θ (n2) entries in edit distance matrix then each entry E (i, j) takes ________ time to compute.
Dynamic Programming is a problem-solving approach in which ________.
In kruskal's algorithm, the next edge is added to viable set A, if its adding does not induce a cycle.
Dijkestra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative cost cycles.
We say that two vertices u and v are mutually not reachable if u can reach v and vice versa.
By breaking any edge on cycle created in free tree, the free ________ is restored.
The difference between Prim’s algorithm and Dijkstra’s algorithm is that Dijkstra’s algorithm uses a different key.
Adding an edge to a free tree creates.
The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the postfix of any other.
Maximum number of vertices in a Directed Graph may be |V2|
The greedy part of the Huffman encoding algorithm is to first find two nodes with larger frequency.
Which is true statement.
In ________ algorithm, at any time, the subset of edges A forms a single tree.
The Huffman algorithm finds a polynomial solution.
Counting sort assumes that the numbers to be sorted are in the range ________.
Although it requires more complicated data structures, Prim's algorithm for a minimum spanning tree is better than Kruskal's when the graph has a large number of vertices.
If a problem is in NP, it must also be in P.
Networks are ________ in the sense that is possible from any location in the network to reach any other location in the digraph.
The ________ given by DFS allow us to determine whether the graph contains any cycles.
A graph may contain ________.
What is generally true of Adjacency List and Adjacency Matrix representations of graphs?
A free tree with n vertices have exactly n+1 edges.
In Prim's algorithm, we start with the root vertex r; it can be any vertex.
The term “coloring” came form the original application which was in architectural design.
You have an adjacency list for G, what is the time compexity to compute Graph transpose G^T?
According to parenthesis lemma. vertex u is a descendent of v vertex if and only if,
Heap sort is a/an ________ and ________ sorting algorithm.
Consider the following adjacency list: Which of the following graph(s) describe(s) the above adjacency list?
We can use the optimal substructure property to devise a ________ formulation of the edit distance problem.
Shortest path problems can be solved efficiently by modeling the road map as a graph.
The Huffman algorithm finds a(n) ________ solution.
In Dynamic Programming, our approach is to ________.
In the clique cover problem, for two vertices to be in the same group, they must be adjacent to each other.
Radix sort is not a non-comparative integer sorting algorithm.
In strong components algorithm, first of all DFS is run for computing finish times of vertices.
Consider three matrices X, Y, Z of dimensions 1 × 2, 2 × 3, 3 × 4 respectively. The number of multiplications of X(YZ) is:
We say that two vertices u and v are mutually ________ if u can reach v and vice versa.
Huffman algorithm uses a greedy approach to generate a postfix code T that minimizes the expected length B(T) of the encoded string.
The Huffman algorithm finds an exponential solution
You have an adjacency list for G, what is the time compexity to compute Graph transpose G^T.?
Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best free edge) when the gaph has relatively few edges.
Dijkstra’s algorithm is operated by maintaining a subset of vertices.
Bellman-Ford allows negative weights edges and negative cost cycles.
Strongly connected components are not affected by reversal of all edges in terms of vertices reachability.
Chain matrix multiplication problem can be solved through ________ strategy.
An optimization problem is one in which you want to find,
Select a course code for Objective Questions:
Select a course code for Subjective Questions: