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