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