Aspire Faculty ID #18860 · Topic: UGC NET Computer Science Nov 2021 (Paper II) · Just now
UGC NET Computer Science Nov 2021 (Paper II)

In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Here, $n$ and $m$ are number of vertices and edges, respectively. Match each algorithm with its time complexity.
List IList II
A. Bellman-Ford algorithmI. $O(m\log n)$
B. Kruskal's algorithmII. $O(n^3)$
C. Floyd-Warshall algorithmIII. $O(n*m)$
D. Topological sortingIV. $O(n+m)$
Choose the correct answer from the options given below:

Solution

Bellman-Ford algorithm checks all edges repeatedly for shortest path, so its time complexity is $O(n*m)$. Thus, $A-III$.

Kruskal's algorithm sorts edges and then applies union-find, so its time complexity is $O(m\log n)$. Thus, $B-I$.

Floyd-Warshall algorithm uses three nested loops for all pairs shortest path, so its time complexity is $O(n^3)$. Thus, $C-II$.

Topological sorting visits vertices and edges once, so its time complexity is $O(n+m)$. Thus, $D-IV$.

Final matching is $A-III,\ B-I,\ C-II,\ D-IV$.

Previous 10 Questions — UGC NET Computer Science Nov 2021 (Paper II)

Nearest first
1
A hash function $h$ defined as $h(key)=key\ mod\ 7$, with linear probing, is used to insert the keys $44,45,79,55,91,18…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
2
The order of a leaf node in a $B+$ tree is the maximum number of value, data record pointer pairs it can hold. Given th…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
3
 Which of the given options provides the increasing order of asymptotic complexity of functions $f_1,\ f_2,\ f_3$ …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
4
Given below are two statementsStatement I: In an undirected graph, number of odd degree vertices is even.Statement II: …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
5
Consider the following graph.Among the following sequencesI. $a\ b\ e\ g\ h\ f$II. $a\ b\ f\ e\ h\ g$III. $a\ b\ f\ h\ …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
6
A data structure is required for storing a set of integers such that each of the following operations can be done in $O…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
7
Two balanced binary trees are given with $m$ and $n$ elements, respectively. They can be merged into a balanced binary …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
8
A double-ended queue (deque) supports adding and removing items from both ends of the queue. The operations supported b…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
9
The postfix form of the expression $(A+B)*(C*D-E)*F/G$ is ______
Topic: UGC NET Computer Science Nov 2021 (Paper II)
10
Given below are two statementsStatement I: LL(1) and LR are examples of Bottom-up parsers.Statement II: Recursive desce…
Topic: UGC NET Computer Science Nov 2021 (Paper II)

Next 10 Questions — UGC NET Computer Science Nov 2021 (Paper II)

Ascending by ID
1
Which agent deals with the happy and unhappy state?
Topic: UGC NET Computer Science Nov 2021 (Paper II)
2
Given below are two statementsStatement I: Breadth-First Search is optimal when all the step costs are equal whereas un…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
3
Consider the given tree below. Calculate the value at the root of the tree using alpha‐beta pruning algorithm.
Topic: UGC NET Computer Science Nov 2021 (Paper II)
4
Which among the following statement(s) is(are) FALSE?A. Greedy best-first search is not optimal but is often efficient.…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
5
Consider the sentence below.There is a country that borders both India and Pakistan.Which of the following logical expr…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
6
Consider a domain consisting of three Boolean variables Toothache, Cavity, and Catch. The full joint distribution is a …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
7
Consider a domain consisting of three Boolean variables Toothache, Cavity, and Catch. The full joint distribution is a …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
8
Consider a domain consisting of three Boolean variables Toothache, Cavity, and Catch. The full joint distribution is a …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
9
Consider a domain consisting of three Boolean variables Toothache, Cavity, and Catch. The full joint distribution is a …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
10
Consider a domain consisting of three Boolean variables Toothache, Cavity, and Catch. The full joint distribution is a …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
Ask Your Question or Put Your Review.

loading...