GATE CS 2022: Algorithm 4 (App update required to attempt this test)

Consider a graph G(V, E) such that every vertex of G is connected to every other vertex through direct link. What is the time complexity to compute the shortest path using Bellman Ford algorithm

Which of the following is true?

I.

T(1) = 0

T(n) = O(n log n)

II.

T(n) = θ (log n)

Consider the following recurrence relation:

What is the time complexity of above recurrence relation?

Consider the following graph:

Among the following sequences:

I. abcdef

II. abfcde

III. cabfed

IV. abdefc

How many are the depth first traversals of the above graph?

In case of quicksort best case, 45 seconds is taken by input size 128 to run. In 4 minutes what size of input can be sorted (In nearest Power of 2)?

The number of comparisons to find 1 to i^Th Minimum using min heap will be______ (suppose i is 100).