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